2333: [SCOI2011]棘手的操作
Description
有N个节点，标号从1到N，这N个节点一开始相互不连通。第i个节点的初始权值为a[i]，接下来有如下一些操作：
U x y: 加一条边，连接第x个节点和第y个节点
A1 x v: 将第x个节点的权值增加v
A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v
A3 v: 将所有节点的权值都增加v
F1 x: 输出第x个节点当前的权值
F2 x: 输出第x个节点所在的连通块中，权值最大的节点的权值
F3: 输出所有节点中，权值最大的节点的权值
Input
输入的第一行是一个整数N，代表节点个数。
接下来一行输入N个整数，a[1], a[2], …, a[N]，代表N个节点的初始权值。
再下一行输入一个整数Q，代表接下来的操作数。
最后输入Q行，每行的格式如题目描述所示。
Output
对于操作F1, F2, F3，输出对应的结果，每个结果占一行。
Sample Input
30 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3
Sample Output
-1010
10
HINT
对于30%的数据，保证 N<=100，Q<=10000
对于80%的数据，保证 N<=100000，Q<=100000
对于100%的数据，保证 N<=300000，Q<=300000
对于所有的数据，保证输入合法，并且 -1000<=v, a[1], a[2], …, a[N]<=1000
【分析】
这题不知道算不算有想法？
还是看了题解，其实也不是很难想，可能是我做的题太少了。 【不会可并堆ORZ】
然后这一题可以离线，因为add的是联通块，而且一旦union也就不会分开了，所以就会希望可以把点重新编号，联通块的编号在一个区间里（因为可以离线）。
所以，先预处理，建一棵合并过程的树，用并查集维护，即连接两个联通块时新建一个点，左右孩子连两个连通块的fa,用dfs序，进行查询，修改。【orz奥爷爷
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define Maxn 300010 int son[*Maxn][];
int a[Maxn],fa[Maxn*]/*,f[Maxn*2]*/,tot;
char s[]; int mymax(int x,int y) {return x>y?x:y;} struct hp
{
int op,x,y,id;
}q[Maxn];int ql; int ffa(int x)
{
if(x!=fa[x]) fa[x]=ffa(fa[x]);
return fa[x];
} int n;
void init()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++) fa[i]=i;tot=n;
int m;
scanf("%d",&m);
ql=;
memset(son,,sizeof(son));
for(int i=;i<=m;i++)
{
scanf("%s",s);
int x,y;
if(s[]=='U')
{
scanf("%d%d",&x,&y);
if(ffa(x)==ffa(y)) continue;
tot++;
son[tot][]=ffa(x);son[tot][]=ffa(y);
fa[tot]=tot;
fa[ffa(x)]=tot;fa[ffa(y)]=tot;
}
else if(s[]=='A'&&s[]=='')
{
scanf("%d%d",&x,&y);
q[++ql].op=;q[ql].x=x;q[ql].y=y;
}
else if(s[]=='A'&&s[]=='')
{
scanf("%d%d",&x,&y);
q[++ql].op=;q[ql].x=x;q[ql].y=y;q[ql].id=ffa(x);
}
else if(s[]=='A')
{
scanf("%d",&x);
q[++ql].op=;q[ql].x=x; }
else if(s[]=='F'&&s[]=='')
{
scanf("%d",&x);
q[++ql].op=;q[ql].x=x;
}
else if(s[]=='F'&&s[]=='')
{
scanf("%d",&x);
q[++ql].op=;q[ql].x=x;q[ql].id=ffa(x);
}
else
{
q[++ql].op=;
}
}
} int cnt,dfn[Maxn],lf[*Maxn],rt[*Maxn];
void dfs(int x)
{
if(x<=n)
{
dfn[x]=++cnt;
lf[x]=rt[x]=dfn[x];
return;
}
dfs(son[x][]);lf[x]=lf[son[x][]];
dfs(son[x][]);rt[x]=rt[son[x][]];
} struct node
{
int l,r,lc,rc,mx;
int lazy;
}t[Maxn*];int len; void upd(int x)
{
if(t[x].lazy==) return;
t[x].mx+=t[x].lazy;
if(t[x].l!=t[x].r)
{
int lc=t[x].lc,rc=t[x].rc;
t[lc].lazy+=t[x].lazy;
t[rc].lazy+=t[x].lazy;
}
t[x].lazy=;
} int build(int l,int r)
{
int x=++len;
t[x].l=l;t[x].r=r;t[x].mx=;
t[x].lazy=;
if(l!=r)
{
int mid=(l+r)>>;
t[x].lc=build(l,mid);
t[x].rc=build(mid+,r);
}
else t[x].lc=t[x].rc=;
return x;
} void add(int x,int l,int r,int y)
{
if(y==) return;
if(t[x].l==l&&t[x].r==r)
{
t[x].lazy+=y;
return;
}
upd(x);
int mid=(t[x].l+t[x].r)>>;
if(r<=mid) add(t[x].lc,l,r,y);
else if(l>mid) add(t[x].rc,l,r,y);
else
{
add(t[x].lc,l,mid,y);
add(t[x].rc,mid+,r,y);
}
int lc=t[x].lc,rc=t[x].rc;
upd(lc);upd(rc);
t[x].mx=mymax(t[lc].mx,t[rc].mx);
} int query(int x,int l,int r)
{
upd(x);
if(t[x].l==l&&t[x].r==r) return t[x].mx;
int mid=(t[x].l+t[x].r)>>;
if(r<=mid) return query(t[x].lc,l,r);
else if(l>mid) return query(t[x].rc,l,r);
else return mymax(query(t[x].lc,l,mid),query(t[x].rc,mid+,r));
} int main()
{
init();
len=;
build(,tot);
cnt=;int ad=;
for(int i=;i<=tot;i++) if(ffa(i)==i)
{
dfs(i);
}
for(int i=;i<=n;i++) add(,dfn[i],dfn[i],a[i]);
for(int i=;i<=ql;i++)
{
if(q[i].op==)
{
// printf("add %d %d %d\n",dfn[q[i].x],dfn[q[i].x],q[i].y);
add(,dfn[q[i].x],dfn[q[i].x],q[i].y);
}
else if(q[i].op==)
{
// printf("add %d %d %d\n",lf[q[i].id],rt[q[i].id],q[i].y);
add(,lf[q[i].id],rt[q[i].id],q[i].y);
}
else if(q[i].op==)
{
ad+=q[i].x;
}
else if(q[i].op==)
{
// printf("ask %d %d\n",dfn[q[i].x],dfn[q[i].x]);
int now=query(,dfn[q[i].x],dfn[q[i].x]);
printf("%d\n",now+ad);
}
else if(q[i].op==)
{
// printf("ask %d %d\n",lf[q[i].id],rt[q[i].id]);
int now=query(,lf[q[i].id],rt[q[i].id]);
printf("%d\n",now+ad);
}
else if(q[i].op==)
{
int now=query(,,cnt);
printf("%d\n",now+ad);
}
}
return ;
}
2016-11-10 09:49:34
学了可并堆我回来更新啦哈哈哈哈【傻。。
【感觉这个题号在嘲笑我><】
左偏树，还要带lazy标记，还要加一个set，呵呵呵，因为看不懂别人的，所以自己YYYYY，所以就乱搞了一整天+很多呆滞的moment。。
细节真心超多，
我搞了个rt（用并查集维护），还有一个fa（左偏树中直属父亲）。
fa，从下往上找，然后从上往下pushdown那里好像有点慢，不过我看黄学长这里也是这样的。【表示左偏树做法比离线慢呐~~
A1操作先删点，再加点，细节很多！！！【因为我乱搞呵呵呵呵
= =或许应该看这个题解：http://blog.csdn.net/charlie_pyc/article/details/20830305
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
#define Maxn 300010
#define INF 0x7fffffff int mymax(int x,int y) {return x>y?x:y;} int a[Maxn],all=;
int n,q,cnt;
char s[]; multiset<int > ss; struct node
{
int x,lc,rc,dis,fa,rt;
int lazy;
}t[Maxn]; void upd(int x)
{
t[x].lc=t[x].rc=;
t[x].dis=;t[x].lazy=;
t[x].fa=;
} void era(int x)
{
multiset<int>:: iterator it;
it=ss.find(x);
ss.erase(it);
} int v[Maxn];
struct Ltree
{
int rtt(int x)
{
if(t[x].rt!=x) t[x].rt=rtt(t[x].rt);
return t[x].rt;
}
void pushdown(int x)
{
if(t[x].lc) t[t[x].lc].lazy+=t[x].lazy;
if(t[x].rc) t[t[x].rc].lazy+=t[x].lazy;
t[x].x+=t[x].lazy;
t[x].lazy=;
}
int merge(int x,int y)
{
if(x==||y==) return x+y;
pushdown(x);pushdown(y);
if(t[x].x<t[y].x) swap(x,y);
t[x].rc=merge(t[x].rc,y);
if(t[x].rc) t[t[x].rc].fa=x;
if(t[t[x].lc].dis<t[t[x].rc].dis) swap(t[x].lc,t[x].rc);
t[x].dis=t[t[x].rc].dis+;
return x;
}
void sol(int x)
{
v[]=;
while(x) v[++v[]]=x,x=t[x].fa;
while(v[]) pushdown(v[v[]--]);
}
int add(int x,int y)
{
int xx=rtt(x);
pushdown(xx);era(t[xx].x);sol(x);
int nw=merge(t[x].lc,t[x].rc);
if(t[x].fa)
{
if(t[t[x].fa].lc==x) t[t[x].fa].lc=nw;
else t[t[x].fa].rc=nw;
}
if(nw)
{
t[nw].fa=t[x].fa;
}
t[x].x+=y;upd(x);
if(x!=xx) nw=merge(x,xx);
else nw=merge(x,nw); t[x].rt=t[xx].rt=t[nw].rt=nw;
pushdown(nw);
ss.insert(t[nw].x);
}
}heap; int main()
{
scanf("%d",&n);
t[].dis=-;
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++) upd(i),t[i].x=a[i],t[i].fa=,t[i].rt=i;
ss.clear();
for(int i=;i<=n;i++) ss.insert(a[i]); scanf("%d",&q);
for(int i=;i<=q;i++)
{
scanf("%s",s);
int x,y;
if(s[]=='U')
{
scanf("%d%d",&x,&y);
int xx=heap.rtt(x),yy=heap.rtt(y);
if(xx==yy) continue;
heap.pushdown(xx);era(t[xx].x);
heap.pushdown(yy);era(t[yy].x);
int nw=heap.merge(xx,yy);
t[xx].rt=t[yy].rt=nw;
heap.pushdown(nw);ss.insert(t[nw].x);
}
else if(s[]=='A')
{
if(s[]=='')
{
scanf("%d%d",&x,&y);
heap.add(x,y);
}
else if(s[]=='')
{
scanf("%d%d",&x,&y);
int xx=heap.rtt(x);
heap.pushdown(xx);
era(t[xx].x);
t[xx].lazy+=y;
heap.pushdown(xx);
ss.insert(t[xx].x);
}
else
{
scanf("%d",&x);
all+=x;
}
}
else
{
if(s[]=='')
{
scanf("%d",&x);
heap.sol(x);
heap.pushdown(x);
printf("%d\n",t[x].x+all);
}
else if(s[]=='')
{
scanf("%d",&x);
int xx=heap.rtt(x);
heap.pushdown(xx);
printf("%d\n",t[xx].x+all);
}
else
{
printf("%d\n",*(--ss.end())+all);
}
}
}
return ;
}
2017-01-20 17:05:47
在后面再写一题：（因为没A就插在AC的题目后面吧）
HDU5454
【题意】
n*n的矩阵，每次对连续的一段对角线全部加1，每次询问一个子矩阵的和（n<=200000）
【分析】
跟那道矩阵旋转的线段树维护有点像。要对矩阵的对角线以及旋转有很深的理解才行啊。。。
对于左斜线来说，加的值都是一样的，右斜线也是。所以可以分开维护。
一个矩形就可以分成一个平行四边形和两个三角形咯，平行四边形那里对角线长度相等，可以求和，三角形的话，对角线长度是递增的，所以可以维护类似a[i]*i的前缀和。。、
超难打ORZ .....
放个还没有AC的代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define INF 0xfffffff
#define Maxn 200010 struct node
{
int l,r,lc,rc,f[],f1[],f2[];
int lazy[];
}t[*Maxn];int len; int n,m;
int myabs(int x) {return x>?x:-x;}
int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} int build(int l,int r)
{
int x=++len;
t[x].l=l;t[x].r=r;
t[x].f[]=t[x].f[]=t[x].f1[]=t[x].f1[]=t[x].f2[]=t[x].f2[]=;
t[x].lazy[]=t[x].lazy[]=;
if(l!=r)
{
int mid=(l+r)>>;
t[x].lc=build(l,mid);
t[x].rc=build(mid+,r);
}
else t[x].lc=t[x].rc=;
return x;
} int gsum(int l,int r)
{
return (l+r)*(r-l+)/;
} void upd(int x,int p)
{
if(t[x].lazy[p]==) return;
int lc=t[x].lc,rc=t[x].rc;
t[x].f[p]+=t[x].lazy[p]*(t[x].r-t[x].l+);
t[x].f1[p]+=t[x].lazy[p]*gsum(t[x].l,t[x].r);
t[x].f2[p]+=t[x].lazy[p]*gsum(*n-t[x].r,*n-t[x].l);
t[lc].lazy[p]+=t[x].lazy[p];t[rc].lazy[p]+=t[x].lazy[p];
t[x].lazy[p]=;
return;
} void change(int x,int l,int r,int p)
{
if(t[x].l==l&&t[x].r==r)
{
t[x].lazy[p]++;
return;
}
upd(x,p);
int mid=(t[x].l+t[x].r)>>;
if(r<=mid) change(t[x].lc,l,r,p);
else if(l>mid) change(t[x].rc,l,r,p);
else
{
change(t[x].lc,l,mid,p);
change(t[x].rc,mid+,r,p);
}
int lc=t[x].lc,rc=t[x].rc;
upd(lc,p);
upd(rc,p);
t[x].f[p]=t[lc].f[p]+t[rc].f[p];
t[x].f1[p]=t[lc].f1[p]+t[rc].f1[p];
t[x].f2[p]=t[lc].f2[p]+t[rc].f2[p];
} int query(int x,int l,int r,int p,int op)
{
int tt;
if(l>r) tt=l,l=r,r=tt;
if(r>*n-) r=*n-;
if(l<) l=;
upd(x,p);
if(t[x].l==l&&t[x].r==r)
{
if(op==) return t[x].f1[p];
else if(op==) return t[x].f2[p];
else return t[x].f[p];
}
int mid=(t[x].l+t[x].r)>>;
if(r<=mid) return query(t[x].lc,l,r,p,op);
else if(l>mid) return query(t[x].rc,l,r,p,op);
else return query(t[x].lc,l,mid,p,op)+query(t[x].rc,mid+,r,p,op);
} int main()
{
int T,kase=;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
len=;
build(,*n-);
printf("Case #%d:\n",++kase);
for(int i=;i<=m;i++)
{
int opt;
scanf("%d",&opt);
int l,r;
if(opt==)
{
scanf("%d%d",&l,&r);
l--;r--;
printf("%d %d %d\n",l,r,);
change(,l,r,);
}
else if(opt==)
{
scanf("%d%d",&l,&r);
l+=n;r+=n;
printf("%d %d %d\n",l,r,);
change(,l,r,);
}
else
{
int a,b;
scanf("%d%d%d%d",&l,&a,&r,&b);
int ans=;
ans+=(query(,a+r-,l+b-,,)+query(,l-r+n,a-b+n,,))*mymin(a-l+,b-r+);
//zhu
int kk=mymin(a+r-,l+b-);
ans+=query(,l+r-,kk,,)-query(,l+r-,kk,,)*(l+r-);//左上
kk=mymax(a+r,l+b);
ans+=query(,kk,a+b-,,)-query(,kk,a+b-,,)*(*n-(a+b-)-);//右下
//fu
kk=mymin(a-b+n-,l-r+n-);
ans+=query(,l-b+n,kk,,)-query(,l-b+n,kk,,)*(l-b+n-);//右上 kk=mymax(a-b+n+,l-r+n+);
ans+=query(,kk,a-r+n,,)-query(,kk,a-r+n,,)*(*n-(a-r+n)-);//左下
printf("%d\n",ans);
}
}
}
return ;
}
有空的话，再填坑吧。。
2016-11-10 09:54:11