首页 > > 程序设计 > C/C++ >

洛谷P3273 [SCOI2011]棘手的操作

2018-06-17 21:30:44来源：未知阅读 ()

题目描述

有N个节点，标号从1到N，这N个节点一开始相互不连通。第i个节点的初始权值为a[i]，接下来有如下一些操作：U x y: 加一条边，连接第x个节点和第y个节点A1 x v: 将第x个节点的权值增加vA2 x v: 将第x个节点所在的连通块的所有节点的权值都增加vA3 v: 将所有节点的权值都增加vF1 x: 输出第x个节点当前的权值F2 x: 输出第x个节点所在的连通块中，权值最大的节点的权值F3: 输出所有节点中，权值最大的节点的权值

输入输出格式

输入格式：

输入的第一行是一个整数N，代表节点个数。接下来一行输入N个整数，a[1], a[2], ..., a[N]，代表N个节点的初始权值。再下一行输入一个整数Q，代表接下来的操作数。最后输入Q行，每行的格式如题目描述所示。

输出格式：

对于操作F1, F2, F3，输出对应的结果，每个结果占一行。

输入输出样例

输入样例#1：复制

输出样例#1：复制

-10
10
10

说明

对于30%的数据，保证 N<=100，Q<=10000

对于80%的数据，保证 N<=100000，Q<=100000

对于100%的数据，保证 N<=300000，Q<=300000

对于所有的数据，保证输入合法，并且 -1000<=v, a[1], a[2], ..., a[N]<=1000

开两个可并堆堆

分别维护联通快最大值和所有的最大值

U x y: 加一条边，连接第x个节点和第y个节点

直接合并

A1 x v: 将第x个节点的权值增加v

先删掉，再加上原来的权值加v

A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v

跟线段树一样打个标记

A3 v: 将所有节点的权值都增加v

直接用一个变量记录

F1 x: 输出第x个节点当前的权值

直接输出

F2 x: 输出第x个节点所在的连通块中，权值最大的节点的权值

找到父亲，输出

F3: 输出所有节点中，权值最大的节点的权值

输出维护最大值的那个堆的根节点

效率暂时rank1

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<iostream>
  5 #include<queue>
  6 using namespace std;
  7 const int MAXN=300010;
  8 #define ls T[x].ch[0]
  9 #define rs T[x].ch[1]
 10 inline int read()
 11 {
 12     int a;
 13     cin>>a;
 14     return a;
 15 }
 16 int root,N,All;
 17 struct Priority
 18 {
 19     struct node
 20     {
 21         int fa,dis,val,ch[2],mark;
 22     }T[MAXN];
 23     void Clear(int x){ls=rs=0;T[x].fa=0;}
 24     void Pushdown(int x)
 25     {
 26         if(ls) T[ls].val+=T[x].mark,T[ls].mark+=T[x].mark;
 27         if(rs) T[rs].val+=T[x].mark,T[rs].mark+=T[x].mark;
 28         T[x].mark=0;
 29     }
 30     int Merge(int x,int y)
 31     {
 32         if(!x||!y)    return x+y;
 33         if( T[x].val < T[y].val)    swap(x,y);
 34         Pushdown(x);
 35         rs=Merge(rs,y);
 36         T[rs].fa=x;
 37         if(T[rs].dis>T[ls].dis) swap(ls,rs);
 38         T[x].dis=T[rs].dis+1;
 39         return x;
 40     }
 41     int Delet(int x)
 42     {
 43         Pushdown(x);
 44         int q=T[x].fa,p=Merge(ls,rs);
 45         T[p].fa=q;
 46         T[q].ch[ T[q].ch[1] == x] = p;
 47         while(q)
 48         {
 49             if(T[ T[q].ch[0] ].dis < T[ T[q].ch[1] ].dis)   swap( T[q].ch[0] , T[q].ch[1] );
 50             if(T[ T[q].ch[1] ].dis+1 == T[q].dis)   return root;
 51             T[q].dis=T[ T[q].ch[1] ].dis+1;
 52             p=q;q=T[q].fa;
 53         }
 54         return p;
 55     }
 56     int Find(int x)
 57     {
 58         while(T[x].fa) x=T[x].fa;
 59         return x;
 60     }
 61     int Sum(int x)
 62     {
 63         int ans=0;
 64         while(x=T[x].fa)  ans+=T[x].mark;
 65         return ans;
 66     }
 67     int AddPoint(int x,int v)
 68     {
 69         int fx=Find(x);
 70         if(fx==x)
 71         {
 72             if(ls+rs==0) 
 73                 {T[x].val+=v;return x;}
 74             else 
 75                 if(ls)  fx=ls;
 76                 else     fx=rs;
 77         }
 78         Delet(x);
 79         T[x].val+=v+Sum(x);
 80         Clear(x);
 81         return Merge(Find(fx),x);
 82     }
 83     int Build()
 84     {
 85         queue<int>q;
 86         for(int i=1;i<=N;i++)  
 87             q.push(i);
 88         while(q.size()>1)
 89         {
 90             int x=q.front();q.pop();
 91             int y=q.front();q.pop();
 92             int z=Merge(x,y);
 93             q.push(z);
 94         }
 95         return q.front();
 96     }
 97 };
 98 Priority h1,h2;
 99 int main()
100 { 
101     #ifdef WIN32
102     freopen("a.in","r",stdin);
103     freopen("b.out","w",stdout);
104     #else
105     #endif
106     char opt[20];
107     N=read();
108     h1.T[0].dis=h2.T[0].dis=-1;
109     for(int i=1;i<=N;i++)
110         h2.T[i].val=h1.T[i].val=read();
111     root=h2.Build();
112     int M=read();
113     while(M--)
114     {
115         scanf("%s",opt+1);
116         if(opt[1]=='U')
117         {
118             int x=read(),y=read();
119             int fx=h1.Find(x),fy=h1.Find(y);
120             if(fx!=fy)
121             {
122                    int tmp=h1.Merge(fx,fy);
123                 if(tmp==fx) root=h2.Delet(fy);
124                 else         root=h2.Delet(fx);//优化,根据大根堆的性质，以后的就没有用了    
125             }
126         }
127         else if(opt[1]=='A')
128         {
129             if(opt[2]=='1')
130             {
131                 int x=read(),v=read();
132                 root=h2.Delet(h1.Find(x));
133                 int y=h1.AddPoint(x,v);
134                 h2.T[y].val=h1.T[y].val;
135                 h2.Clear(y);
136                 root=h2.Merge(root,y);
137             }
138             else if(opt[2]=='2')
139             {
140                 int x=read(),v=read();
141                 int fx=h1.Find(x);
142                 root=h2.Delet(fx);
143                 h1.T[fx].val+=v;
144                 h1.T[fx].mark+=v;
145                 h2.T[fx].val=h1.T[fx].val;
146                 h2.Clear(fx);
147                 root=h2.Merge(root,fx);
148             }
149             else if(opt[2]=='3')
150             {
151                 int v=read();
152                 All+=v;
153             }
154             
155         }
156         else if(opt[1]=='F')
157         {
158             if(opt[2]=='1')
159             {
160                 int x=read();
161                 printf("%d\n",h1.T[x].val+h1.Sum(x)+All);
162             }
163             else if(opt[2]=='2')
164             {
165                 int x=read();
166                 printf("%d\n",h1.T[h1.Find(x)].val+All);
167             }
168             else if(opt[2]=='3')
169                 printf("%d\n",h2.T[root].val+All);
170         }
171     }
172 }