吐槽
上午风浔凌julao问我的神题
操作又多又毒瘤又棘手。。。
然后bzoj题号正好是2333，2333333333
思路
貌似只有我是这么写的
线段树合并，
每个线段树存每个连通块的信息，维护点的值，然后并查集维护。。
然后内存被卡，手写一发内存池
然后TLE了，加上O2终于过了
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
int fa[300010],Nodecnt,root[300010],n,q,alladd;
struct Node{
int lson,rson;
short maxx,tag;
}Seg[300000*25];
int pool[300000*20],top=0;
inline char Getchar() {
static char buf[(1<<16)], *p1 = buf, *p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<16),stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
int x=0,f=1;
char ch=Getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=Getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=Getchar();
}
return x*f;
}
int getnew(void){
if(top){
int t=pool[top];
top--;
Seg[t].lson=Seg[t].rson=Seg[t].maxx=Seg[t].tag=0;
return t;
}
return ++Nodecnt;
}
void throwin(int x){
pool[++top]=x;
}
int find(int x){
if(fa[x]==x)
return x;
else return fa[x]=find(fa[x]);
}
void pushup(int o){
Seg[o].maxx=max(Seg[Seg[o].lson].maxx,Seg[Seg[o].rson].maxx);
}
void pushdown(int o){
if(Seg[o].tag){
if(Seg[o].lson){
Seg[Seg[o].lson].tag+=Seg[o].tag;
Seg[Seg[o].lson].maxx+=Seg[o].tag;
}
if(Seg[o].rson){
Seg[Seg[o].rson].tag+=Seg[o].tag;
Seg[Seg[o].rson].maxx+=Seg[o].tag;
}
Seg[o].tag=0;
}
}
void merge(int x,int y,int l,int r,int &o){
pushdown(x);
pushdown(y);
if(x*y==0){
o=x+y;
return;
}
if(l==r){
o=getnew();
Seg[o].maxx=max(Seg[x].maxx,Seg[y].maxx);
throwin(x);
throwin(y);
return;
}
o=getnew();
Seg[o].maxx=max(Seg[x].maxx,Seg[y].maxx);
int mid=(l+r)>>1;
merge(Seg[x].lson,Seg[y].lson,l,mid,Seg[o].lson);
merge(Seg[x].rson,Seg[y].rson,mid+1,r,Seg[o].rson);
throwin(x);
throwin(y);
}
void add(int l,int r,int &o,int pos,int val){
// printf("l=%d r=%d o=%d pos=%d val=%d
",l,r,o,pos,val);
if(!o)
o=getnew();
// printf("l=%d r=%d o=%d pos=%d val=%d
",l,r,o,pos,val);
if(l==r){
Seg[o].maxx+=val;
return;
}
pushdown(o);
// printf("ok
");
int mid=(l+r)>>1;
if(pos<=mid)
add(l,mid,Seg[o].lson,pos,val);
else
add(mid+1,r,Seg[o].rson,pos,val);
pushup(o);
}
void erase(int l,int r,int &o,int pos){
pushdown(o);
if(l==r){
throwin(o);
o=0;
return;
}
// printf("ok
");
int mid=(l+r)>>1;
if(pos<=mid){
erase(l,mid,Seg[o].lson,pos);
if((!Seg[o].rson)&&(!Seg[o].lson)){
throwin(o);
o=0;
}
}
else{
erase(mid+1,r,Seg[o].rson,pos);
if((!Seg[o].rson)&&(!Seg[o].lson)){
throwin(o);
o=0;
}
}
pushup(o);
}
void debug(int l,int r,int o){
if(!o)
return;
printf("l=%d r=%d tag=%d o=%d max=%d
",l,r,Seg[o].tag,o,Seg[o].maxx);
if(l!=r){
int mid=(l+r)>>1;
debug(l,mid,Seg[o].lson);
debug(mid+1,r,Seg[o].rson);
}
}
void uni(int x,int y){
if(find(x)!=find(y)){
erase(1,n,root[n+1],find(x));
erase(1,n,root[n+1],find(y));
int t=0;
merge(root[find(x)],root[find(y)],1,n,t);
root[find(y)]=t;
fa[find(x)]=find(y);
// debug(1,n,root[find(y)]);
add(1,n,root[n+1],find(y),Seg[root[find(y)]].maxx);
}
}
int query(int l,int r,int o,int pos){
if(l==r){
return Seg[o].maxx;
}
pushdown(o);
int mid=(l+r)>>1;
if(pos<=mid)
return query(l,mid,Seg[o].lson,pos);
else
return query(mid+1,r,Seg[o].rson,pos);
}
int main(){
freopen("8.in","r",stdin);
freopen("test.out","w",stdout);
// scanf("%d",&n);
n=read();
Seg[0].maxx=-0x3f3f3f3f;
for(int i=1;i<=n;i++)
fa[i]=i,root[i]=0;
for(int i=1;i<=n;i++){
int midx;
// scanf("%d",&midx);
midx=read();
add(1,n,root[i],i,midx);
add(1,n,root[n+1],i,midx);
}
// scanf("%d",&q);
q=read();
char opt[4];
for(int i=1;i<=q;i++){
opt[0]=Getchar();
while(opt[0]!='U'&&opt[0]!='A'&&opt[0]!='F')
opt[0]=Getchar();
if(opt[0]=='U'){
int x,y;
// scanf("%d %d",&x,&y);
x=read();
y=read();
uni(x,y);
continue;
}
opt[1]=Getchar();
while(opt[1]!='1'&&opt[1]!='2'&&opt[1]!='3')
opt[1]=Getchar();
if(opt[0]=='A'&&opt[1]=='1'){
int x=read(),v=read();
// scanf("%d %d",&x,&v);
erase(1,n,root[n+1],find(x));
add(1,n,root[find(x)],x,v);
add(1,n,root[n+1],find(x),Seg[root[find(x)]].maxx);
continue;
}
else if(opt[0]=='A'&&opt[1]=='2'){
int x=read(),v=read();
// scanf("%d %d",&x,&v);
add(1,n,root[n+1],find(x),v);
Seg[root[find(x)]].maxx+=v;
Seg[root[find(x)]].tag+=v;
pushdown(root[find(x)]);
continue;
}
else if(opt[0]=='A'&&opt[1]=='3'){
int v=read();
alladd+=v;
continue;
}
else if(opt[0]=='F'&&opt[1]=='1'){
int x=read();
printf("%d
",query(1,n,root[find(x)],x)+alladd);
continue;
}
else if(opt[0]=='F'&&opt[1]=='2'){
int x=read();
printf("%d
",Seg[root[find(x)]].maxx+alladd);
continue;
}
else{
printf("%d
",Seg[root[n+1]].maxx+alladd);
continue;
}
}
return 0;
}