CF527C Glass Carving

开四个set,分别存切割的刀以及每个区间段,然后每次各自从行和列取最长的区间段,乘一起即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;


ll w,h;
std::set<ll> st[2];
std::multiset<ll> sm[2];
std::multiset<ll>::iterator it;

inline void init(){
	char ch[5];ll x,l,r;int id;
	std::cin>>ch+1;scanf("%lld",&x);
	id=(ch[1]=='H');
	set<ll> &nst=st[id];
	multiset<ll> &nsm=sm[id];
	nst.insert(x);
	it=nst.find(x);
	--it;l=*it;
	++it,++it;r=*it;
	it=nsm.find(r-l);
	nsm.erase(it);nsm.insert(r-x);nsm.insert(x-l);
	it=sm[0].end();--it;l=*it;
	it=sm[1].end();--it;r=*it;
	printf("%lld\n",l*r);
}

int main(){
	scanf("%lld%lld",&w,&h);
	int T;
	scanf("%d",&T);
	st[0].insert(0),st[0].insert(w);
	st[1].insert(0),st[1].insert(h);
	sm[0].insert(w),sm[1].insert(h);
	while(T--){
		init();
	}
	return 0;
}

lp1438 无聊的数列

区间加上一个等差数列这件事情其实并不好维护。但既然是单点查询,那就可以考虑差分。
我们考虑将数列差分,维护一个差分数列。于是区间 [l,r] 加上等差数列 {K,D},就变成了三个操作:
点 l 加上 K
区间 [l+1,r] 加上 D
点 r+1 减去 K+(r-l)*D
对于每个查询求前缀和即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

const int N=100005;
int n,m;
ll a[N];
ll val[N<<2],tag[N<<2];
inline void pshd(int L,int R,int X){
	int MID=(L+R)>>1;
	tag[X<<1]+=tag[X];tag[X<<1|1]+=tag[X];
	val[X<<1]+=tag[X]*(MID-L+1);val[X<<1|1]+=tag[X]*(R-MID);
	tag[X]=0;
}
inline void updt(int X){
	val[X]=val[X<<1]+val[X<<1|1];
}
ll qry(int L,int R,int A,int B,int X){
	if(A<=L&&B>=R){
		return val[X];
	}
	int MID=(L+R)>>1;ll ret=0;
	pshd(L,R,X);
	if(A<=MID){
		ret+=qry(L,MID,A,B,X<<1);
	}
	if(B>MID){
		ret+=qry(MID+1,R,A,B,X<<1|1);
	}
	return ret;
}
void mdf(int L,int R,int A,int B,int X,ll V){
	if(A<=L&&B>=R){
		tag[X]+=V;
		val[X]+=V*(R-L+1);
		return;
	}
	int MID=(L+R)>>1;
	pshd(L,R,X);
	if(A<=MID){
		mdf(L,MID,A,B,X<<1,V);
	}
	if(B>MID){
		mdf(MID+1,R,A,B,X<<1|1,V);
	}
	updt(X);
}
void build(int L,int R,int X){
	if(L==R){
		val[X]=a[L];
		return;
	}
	int MID=(L+R)>>1;
	build(L,MID,X<<1);
	build(MID+1,R,X<<1|1);
	updt(X);
}
inline void chg(int L,int R,ll V){
	if(L>R||L<1||R>n){
		return;
	}
	mdf(1,n,L,R,1,V);
}
inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=n;i>1;--i){
		a[i]-=a[i-1];
	}
	build(1,n,1);
	ll opt,l,r,k,d,p;
	for(int i=1;i<=m;++i){
		scanf("%lld",&opt);
		if(opt==1){
			scanf("%lld%lld%lld%lld",&l,&r,&k,&d);
			chg(l,l,k);chg(l+1,r,d);chg(r+1,r+1,-(k+d*(r-l)));
		}else{
			scanf("%lld",&p);
			printf("%lld\n",qry(1,n,1,p,1));
		}
	}
}

int main(){
	init();
	return 0;
}

lp3313 SDOI2014 旅行

虽然这一题被划在主席树下面,但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。
树链剖分后我们考虑对每一条链,建很多棵线段树,每棵线段树表示这条链上某种颜色的情况,然后大力合并。复杂度显然是对的。
关键是如何动态开点。本质上动态开点长得就和主席树差不多(这可能是为什么这题会被放在主席树下面),但是可能存在很多细节。
另:我的线段树区间查询写成依次单点查询,居然跑到了1.2s,让我一度以为是我常数问题…甚至差点卡进去了。精彩。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline int rd(){
	char ch=getchar();int r=0;
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){r=r*10+ch-'0';ch=getchar();}
	return r;
}
const int N=100005;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);Eadd(V,U);
}
int n,m;
int val[N],clr[N],dep[N],sz[N],sn[N],fa[N],dfn[N],cnt=0,tp[N];
inline void dfs0(int X){
	dep[X]=dep[fa[X]]+1;sz[X]=1;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){continue;}
		fa[e[i].v]=X;
		dfs0(e[i].v);
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	dfn[X]=++cnt;
	if(sn[X]){tp[sn[X]]=tp[X];dfs1(sn[X]);}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]||e[i].v==fa[X]){continue;}
		tp[e[i].v]=e[i].v;dfs1(e[i].v);
	}
}
#define MID ((L+R)>>1)
struct Node{
	int l;int r;int sm;int mx;
}tr[4000005];
int rt[N];
int tcnt=0;
inline void chg(int &NW,int L,int R,int P,int V){
	if(!NW){NW=++tcnt;}
	if(L==R){tr[NW].sm=V,tr[NW].mx=V;return;}
	P<=MID?(chg(tr[NW].l,L,MID,P,V)):(chg(tr[NW].r,MID+1,R,P,V));
	tr[NW].sm=tr[tr[NW].l].sm+tr[tr[NW].r].sm;tr[NW].mx=Max(tr[tr[NW].l].mx,tr[tr[NW].r].mx);
}
inline int qryMx(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].mx;}//此处不应写成L==R 
	return Max((A<=MID?qryMx(tr[X].l,A,B,L,MID):0),(B>MID?qryMx(tr[X].r,A,B,MID+1,R):0));
}
inline int qrySm(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].sm;}
	return (A<=MID?qrySm(tr[X].l,A,B,L,MID):0)+(B>MID?qrySm(tr[X].r,A,B,MID+1,R):0);
}
inline void ADD(int X,int P,int V){
	chg(rt[X],1,n,P,V);
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		val[i]=rd(),clr[i]=rd();
	}
	int u,v;
	for(int i=1;i<n;++i){
		u=rd(),v=rd();
		add(u,v);
	}
	sz[0]=0;fa[1]=0;
	dfs0(1);
	tp[1]=1;
	dfs1(1);
	for(int i=1;i<=n;++i){
		ADD(clr[i],dfn[i],val[i]);
	}
	char ch[10];
	int x,y,c;
	for(int i=1;i<=m;++i){
		std::cin>>ch+1;
		switch(ch[2]){
			case 'C':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],0);
				ADD(clr[x]=y,dfn[x],val[x]);
				break;
			}
			case 'W':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],val[x]=y);
				break;
			}
			case 'S':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT+=qrySm(rt[c],dfn[tp[x]],dfn[x],1,n);
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT+=qrySm(rt[c],dfn[y],dfn[x],1,n);
				printf("%d\n",RT);
				break;
			}
			case 'M':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT=Max(RT,qryMx(rt[c],dfn[tp[x]],dfn[x],1,n));
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT=Max(RT,qryMx(rt[c],dfn[y],dfn[x],1,n));
				printf("%d\n",RT);
				break;
			}
		}
	}
}
int main(){
//	freopen("33132.in","r",stdin);
//	freopen("33132.ans","w",stdout);
	init();
	return 0;
}

lp3168 CQOI2015 任务查询系统

观察题面,我们发现这是一道变态题:区间加点,单点查询第k大,强制在线——这tm不是变态题么!别的不说,权值怎么离散化我都不会。
仔细一看,真的是这样么?
我们发现,先是m个修改,后面再跟着n个询问!这意味着什么?这意味着所谓的区间修改事实上是fake的,因为我们事实上只要对最后一个版本进行询问。
经验上,多次区间修改后求单点值,我们使用差分+前缀和来维护。在这里同样是生效的,只需把每一次修改拆成两次即可。
修改可以用一些妙妙方式储存,比如说Vector或者手写邻接表。
那就是主席树裸题了。

注意:每一次修改的时候修改的仅仅是L和R+1两个点,但是这并不是正确的!在把修改排序之后,每一个修改是从它的上一个点复制版本,但上一个版本可能并没有任何修改,这也就意味着,上一个版本可能是空的!这就完全不是前缀和了。
应当如何做呢?每一个点应当预先从前一个点复制。这样哪怕这个点没有被修改,也仍然能保持它的性质。
另外,离散化的时候不应该把点离散化在一起。在这里,把值相同的点离散化到不同的位置并不会影响答案。事实上,如果把值相同的点离散化到相同的位置,反而会更麻烦。这是因为如果离散化到相同的位置,那么这三个点在线段树上就存在同一个点里了。这时候,倘若这个点的大小为3,而你需要查询前2大的和,你就无法处理了。这平白增加了实现的复杂度。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector> 
using namespace std;

typedef long long ll; 
const int N=100005;
inline int Abs(int X){
	return X>0?X:-X;
}
#define MID ((L+R)>>1) 
vector<int> lst[N];
struct data{
	int l;int r;int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
int loc[N],vl[N];
int n,m;
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;ll sm;
		}tr[N*160];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,ll V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+(V>0?1:-1);tr[NW].sm=tr[LST].sm+(V>0?loc[V]:-loc[-V]);
			if(L==R){return;}
			Abs(V)<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline ll qry(int X,int L,int R,ll V){
			ll RT=0;
			while(L<R){
//				printf("%lld %d %d %d %lld %d\n",RT,X,L,R,V,tr[X].sz);
				(tr[tr[X].l].sz<V)?(L=MID+1,V-=tr[tr[X].l].sz,RT+=tr[tr[X].l].sm,X=tr[X].r):(R=MID,X=tr[X].l);
			}
			RT+=tr[X].sm;
			return RT;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			printf("%d|%lld ",tr[X].sz,tr[X].sm);
			prnt(tr[X].l);prnt(tr[X].r);
		}
	public:
		inline void ADD(int X,ll V){
			int nw;
			if(!rt[X]){
				bld(rt[X-1],rt[X],1,100000,V);
			}else{
				bld(rt[X],nw,1,100000,V);
				rt[X]=nw;
			}
		}
		inline ll QRY(int X,int V){
//			printf("qry:%d %d %d\n",X,V,tr[rt[X]].sz);
			return V>tr[rt[X]].sz?tr[rt[X]].sm:qry(rt[X],1,100000,V);
		}
		inline void RNW(int X){
			if(!rt[X]){
				rt[X]=rt[X-1];
			}
		}
		inline void PRNT(int X){
			prnt(rt[X]);
		}
		inline void prpr(){
			cnt=0;
			tr[0].sz=tr[0].sm=0;
			for(int i=1;i<=n;++i){
				rt[i]=0;
			}
		}
}TR;
void init(){
	TR.prpr();
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
	}
	std::sort(a+1,a+1+m,cmp);
	vl[0]=0,a[0].val=0;
	for(int i=1;i<=m;++i){
		vl[i]=vl[i-1]+1;
		loc[vl[i]]=a[i].val;
	}
	for(int i=1;i<=m;++i){
		lst[a[i].l].push_back(vl[i]);
		lst[a[i].r+1].push_back(-vl[i]);
	}
	for(int i=1;i<=n;++i){
		TR.RNW(i);
		for(int j=0;j<lst[i].size();++j){
			TR.ADD(i,lst[i][j]);
		}
	}
	int x,a,b,c,v;ll lans=1;
	for(int i=1;i<=n;++i){
		scanf("%d%d%d%d",&x,&a,&b,&c);
		v=(1ll*lans*a+b)%c+1;
		printf("%lld\n",lans=TR.QRY(x,v));
	}
}
int main(){
	init();
	return 0;
}

lp3302 SDOI2013 森林

我们发现,树上的链上第k大是可以使用主席树来维护的。对于每一个节点,我们从它的父亲复制一个版本,然后每一次求出LCA以后对链的两个端点、链的LCA、链的父亲分别查询。之后统计答案即可。
对于有连边操作的树,我们可能可以想到用LCT来维护。但是代码难度太高,而且事实上我也不知道要怎么写。所以我们可以考虑一种类似于按秩合并的操作,也就是说,每一次,我们把子树大小较小的子树合并到子树大小较大的子树。对于较小的那棵树,我们暴力更新其中的每一个节点。于是可以证明,每个节点的被更新次数最多不超过log次。
这样我们就有了一个\(O(nlog^2n)\)的做法。
注意:主席树的L,R本身就是节点位置;合并的时候要记得更新小树的根节点;返回的值是第k大的值而非第k大的排名因而要逆离散化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;

const int N=80005;
struct data{
	int id;
	int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
inline bool cmp2(const data &A,const data &B){
	return A.id<B.id;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V),Eadd(V,U);
}
#define MID (L+R>>1)
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;
		};
		Node tr[30000000];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,int V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+1;
			if(L==R){return;}
			V<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline int qry(int A,int B,int C,int D,int L,int R,int V){
			while(L<R){
//				printf("nw:%d %d %d %d %d\n",A,B,C,D,V);
				(tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz<V)?
				(V-=tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz,L=MID+1,A=tr[A].r,B=tr[B].r,C=tr[C].r,D=tr[D].r):
				(R=MID,A=tr[A].l,B=tr[B].l,C=tr[C].l,D=tr[D].l);
			}
			return L;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].l);
			prnt(tr[X].r);
			printf("%d ",tr[X].sz);
		}
	public:
		inline void ADD(int LST,int VER,int V){
			bld(rt[LST],rt[VER],1,80000,V);
		}
		inline int QRY(int A,int B,int C,int D,int V){
			return qry(rt[A],rt[B],rt[C],rt[D],1,80000,V);
		}
		inline void prpr(){
			cnt=0;
		}
		inline void pt(int X){
			prnt(rt[X]);
		}
}TR;
int vis[N],fa[N][20],sz[N],dep[N],loc[N];
inline void dfs0(int X){
//	printf("\t\t\tdfs0(%d)%d\n",X,dep[X]);
	vis[X]=sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]){
			continue;
		}
		fa[e[i].v][0]=X;
		dep[e[i].v]=dep[X]+1;
		for(int j=1;j<=18;++j){
			fa[e[i].v][j]=fa[fa[e[i].v][j-1]][j-1];
		}
		TR.ADD(X,e[i].v,a[e[i].v].val);
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	vis[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			continue;
		}
		dfs1(e[i].v);
	}
}
inline int szq(int X){
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=0){
			X=fa[X][i];
		}
	}
	return sz[X];
}
inline void uni(int X,int Y){
	int SZ=szq(X);
	dfs1(X);
	add(X,Y);
	fa[X][0]=Y;
	dep[X]=dep[Y]+1;
	TR.ADD(Y,X,a[X].val);
	for(int i=1;i<=18;++i){
		fa[X][i]=fa[fa[X][i-1]][i-1];
	}
	int RT=X;
	for(int i=18;i>=0;--i){
		if(fa[RT][i]){
			RT=fa[RT][i];
		}
	}
	sz[RT]+=SZ;
	dfs0(X);
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		X^=Y^=X^=Y;
	}
	for(int i=18;i>=0;--i){
		if(dep[fa[X][i]]>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
int n,m,q,tid;
void init(){
	scanf("%d",&tid);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i].val);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i){
		loc[i]=a[i].val;
	}
	for(int i=1;i<=n;++i){
		if(a[i].val!=a[i-1].val){
			a[i].val=a[i-1].val+1;
		}else{
			a[i].val=a[i-1].val;
		}
	}
	std::sort(a+1,a+1+n,cmp2); 
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	TR.prpr();
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			dep[i]=1;
			TR.ADD(0,i,a[i].val);
			dfs0(i);
		}
	}
//	for(int i=1;i<n;++i){
//		printf("%d:",i);
//		TR.pt(i);
//		puts("");
//	}
	int lans=0,x,lc;
	char ch[10];
	for(int i=1;i<=q;++i){
		cin>>ch+1;
		switch(ch[1]){
			case 'Q':{
				scanf("%d%d%d",&u,&v,&x);
				u^=lans,v^=lans,x^=lans;
				lc=lca(u,v);
//				printf("\t\t\t%d %d %d\n",u,v,x);
				printf("%d\n",lans=loc[TR.QRY(fa[lc][0],u,lc,v,x)]);
				break; 
			}
			case 'L':{
				scanf("%d%d",&u,&v);
				u^=lans,v^=lans;
//				printf("\t\t\t%d %d\n",u,v);
				if(szq(u)>szq(v)){
					u^=v^=u^=v;
				}
				uni(u,v);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp2146 NOI2015 软件包管理器

简化题意:
存在一棵树,其上所有点的初始值为0。
存在两种操作,分别是,将一个点的所有父亲节点改为1,或者将一个点的所有儿子节点改为0。
要求维护这个修改,并能得知每一次修改的节点个数。
当然地,考虑到这棵树是静态的,我们可以预处理出每个点的子树大小和它到根的路径长度。
于是,问题就转化为:
把目标节点到根节点的所有点变成1,把目标节点的子树变成0,查询目标节点到根节点的1的数量,查询目标节点的子树的1的数量。
这个问题似乎有些困难。我们考虑它的弱化版,也就是只有目标节点到根节点的这样一种情况。
显然,只需要上一个树剖就可以解决问题。
那么加上子树修改呢?
我们意识到一个很有趣的事情,那就是,一棵子树中的点,在树剖后,仍然是DFS序序列上连续的一段。又,这一段的长度显然是子树大小,由此问题可解。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) 

const int N=100005;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
int n,q;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}
int sz[N],sn[N],dep[N],fa[N];
inline void dfs0(int X,int FA){
	sz[X]=1,sn[X]=0,dep[X]=dep[FA]+1,fa[X]=FA;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
int dfn[N],cnt=0,tp[N]; 
inline void dfs1(int X,int FA,int TP){
	tp[X]=TP,dfn[X]=++cnt;
	if(sn[X]){
		dfs1(sn[X],X,TP);
	}
	Fv(i,X){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,X,e[i].v);
	}
}

#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
int tr[N<<2],tg[N<<2];
inline void rnw(int X,int L,int R,int C){
	tr[X]=LEN*C,tg[X]=C+1;
}
inline void updt(int X,int L,int R){
	tr[X]=tr[LS]+tr[RS];
}
inline void pshd(int X,int L,int R){
	if(tg[X]){
		rnw(LS,L,MID,tg[X]-1),rnw(RS,MID+1,R,tg[X]-1);
		tg[X]=0;
	}
}
inline void chg(int X,int L,int R,int A,int B,int C){
	if(A<=L&&R<=B){
		rnw(X,L,R,C);
		return;
	}
	if(R<A||L>B){
		return;
	}
	pshd(X,L,R);
	chg(LS,L,MID,A,B,C),chg(RS,MID+1,R,A,B,C);
	updt(X,L,R);
}
inline int qry(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		return tr[X];
	}
	if(R<A||L>B){
		return 0;
	}
	pshd(X,L,R);
	return qry(LS,L,MID,A,B)+qry(RS,MID+1,R,A,B);
}

inline int dwqry(int X){
	return qry(1,1,n,dfn[X],dfn[X]+sz[X]-1);
}
inline void dwchg(int X){
	chg(1,1,n,dfn[X],dfn[X]+sz[X]-1,0);
}
inline int up(int X){
	int RT=0;
	while(X){
		RT-=qry(1,1,n,dfn[tp[X]],dfn[X]);
		RT+=dfn[X]-dfn[tp[X]]+1;
		chg(1,1,n,dfn[tp[X]],dfn[X],1);
		X=fa[tp[X]];
	}
	
	return RT;
}
void init(){
	scanf("%d",&n);
	int x;
	for(int i=1;i<n;++i){
		scanf("%d",&x);
		add(i+1,x+1);
	}
	dfs0(1,0);
	dfs1(1,0,1);
	scanf("%d",&q);
	char ch[10];
	for(int i=1;i<=q;++i){
		std::cin>>ch+1;
		scanf("%d",&x);
		++x;
		if(ch[1]=='i'){
			printf("%d\n",up(x));
		}else{
			printf("%d\n",dwqry(x));
			dwchg(x);
		}
	}
}
int main(){
	init();
	return 0;
}

lp2486 SDOI2011 染色

考虑这一题在链上的情况。
显然,可以建一棵线段树,修改是打标记下传,查询是左右相加特判左右相邻处颜色是否相同。
看起来在树上也可以这么做。但是仔细想想会发现不太对。
这是因为,根据树链剖分的原理,每两条剖开的链是独立查询的。
因此,在树上查询的时候,需要额外查询两个相接的链的接驳处的颜色是否相同。
这大概就做完了。

然后我们发现实时查询接驳处的颜色不仅很傻,而且容易错。
所以我们考虑开两个数组:lc和rc,储存一个区间内左端颜色和右端颜色。

另外就是链上接驳处的颜色问题。一种容易想到的方法是每一次记录它来的那个点,然后比较来的那个点和自身。
然而这么做同样是不仅傻而且容易错的。于是我们考虑另一种方法:每一次比较链顶和链顶的父亲这两个点,并将它的负贡献预先扣除。这样可以有效简化代码。

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)

inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}
int n,m;
const int N=100005;
struct ee{
    int v;
    int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
    e[++et]=(ee){V,h[U]};
    h[U]=et;
} 
inline void add(int U,int V){
    Eadd(U,V);
    Eadd(V,U);
}
int sn[N],sz[N],fa[N],dep[N];
inline void dfs0(int X,int FA){
    fa[X]=FA;sz[X]=1;dep[X]=dep[FA]+1;sn[X]=0;
    Fv(i,X){
        if(e[i].v==FA){
            continue;
        }
        dfs0(e[i].v,X);
        if(sz[e[i].v]>sz[sn[X]]){
            sn[X]=e[i].v;
        }
        sz[X]+=sz[e[i].v];
    }
}
int dfn[N],tp[N],cnt=0;
inline void dfs1(int X,int FA,int TP){
    dfn[X]=++cnt;tp[X]=TP;
    if(sn[X]){
        dfs1(sn[X],X,TP);
    }
    Fv(i,X){
        if(e[i].v==FA||e[i].v==sn[X]){
            continue;
        }
        dfs1(e[i].v,X,e[i].v);
    }
}
int clr[N];
#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
int tr[N<<2],tg[N<<2],val[N<<2],lc[N<<2],rc[N<<2];
inline void mdf(int X,int C){
    tr[X]=tg[X]=lc[X]=rc[X]=C;
    val[X]=1;
}
inline void pshd(int X,int L,int R){
	if(L==R){
		return;
	}
    if(tg[X]){
        mdf(LS,tg[X]),mdf(RS,tg[X]);
        tg[X]=0;
    }
}
inline int qryc(int X,int L,int R,int P){
    if(L==R){
        return tr[X];
    }
    pshd(X,L,R);
    return P<=MID?qryc(LS,L,MID,P):qryc(RS,MID+1,R,P);
}
inline void updt(int X,int L,int R){
    val[X]=(val[LS]+val[RS]-(rc[LS]==lc[RS]));
    lc[X]=lc[LS],rc[X]=rc[RS];
}
inline void chg(int X,int L,int R,int A,int B,int C){
    if(A<=L&&R<=B){
        mdf(X,C);
        return;
    }
    if(L>B||R<A){
        return;
    }
    pshd(X,L,R);
    chg(LS,L,MID,A,B,C);chg(RS,MID+1,R,A,B,C);
    updt(X,L,R);
}
inline int qryv(int X,int L,int R,int A,int B){
    if(A<=L&&R<=B){
        return val[X];
    }
    if(L>B||R<A){
        return 0;
    }
    pshd(X,L,R);
    return qryv(LS,L,MID,A,B)+qryv(RS,MID+1,R,A,B)-((A<=MID&&B>MID)?(rc[LS]==lc[RS]):0);
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&clr[i]);
    }
    int u,v;
    for(int i=1;i<n;++i){
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    sz[0]=0,dep[0]=0;
    dfs0(1,0);
    dfs1(1,0,1);
    for(int i=1;i<=n;++i){
        chg(1,1,n,dfn[i],dfn[i],clr[i]);
    }
    char ch[4];
    int c,ans;
    for(int i=1;i<=m;++i){
        std::cin>>ch+1;
        switch(ch[1]){
            case 'Q':{
                scanf("%d%d",&u,&v);
                ans=0;
                while(tp[u]!=tp[v]){
                    if(dep[tp[u]]<dep[tp[v]]){
                        Swap(u,v);
                    }
                    ans+=qryv(1,1,n,dfn[tp[u]],dfn[u]);
                    ans-=(qryc(1,1,n,dfn[tp[u]])==qryc(1,1,n,dfn[fa[tp[u]]]));
                    u=fa[tp[u]];
                }
                if(dep[u]<dep[v]){
                    Swap(u,v);
                }
                ans+=qryv(1,1,n,dfn[v],dfn[u]);
                printf("%d\n",ans);
                break;
            }
            case 'C':{
                scanf("%d%d%d",&u,&v,&c);
                while(tp[u]!=tp[v]){
                    if(dep[tp[u]]<dep[tp[v]]){
                        Swap(u,v);
                    }
                    chg(1,1,n,dfn[tp[u]],dfn[u],c);
                    u=fa[tp[u]];
                }
                if(dep[u]<dep[v]){
                    Swap(u,v);
                }
                chg(1,1,n,dfn[v],dfn[u],c);
                break;
            }
        }
    }
}

int main(){
    init();
    return 0;
}

lp2590 ZJOI2008 树的统计

树剖套线段树裸题。

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
using namespace std;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=30005;
const int INF=2147483647;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int dep[N],fa[N],sz[N],sn[N],tp[N],dfn[N];
int val[N],n;
inline void dfs0(int X,int FA){
	sz[X]=1,sn[X]=0;
	fa[X]=FA;dep[X]=dep[FA]+1;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
	}
}
int cnt=0;
inline void dfs1(int X,int FA,int TP){
	tp[X]=TP;
	dfn[X]=++cnt;
	if(sn[X]){
		dfs1(sn[X],X,TP);
	}
	Fv(i,X){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,X,e[i].v);
	}
}

#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
int tr[240005],mx[240005];
inline void updt(int X){
	tr[X]=tr[LS]+tr[RS];
	mx[X]=Max(mx[LS],mx[RS]);
}
inline void chg(int X,int L,int R,int P,int V){
	if(L==R){
		tr[X]=mx[X]=V;
		return;
	}
	P<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);
	updt(X);
	return;
}
inline int qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X];
	}
	if(R<A||L>B){
		return 0;
	}
	return qrySm(LS,L,MID,A,B)+qrySm(RS,MID+1,R,A,B);
}
inline int qryMx(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return mx[X];
	}
	if(R<A||L>B){
		return -INF;
	}
	return Max(qryMx(LS,L,MID,A,B),qryMx(RS,MID+1,R,A,B));
}

void init(){
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	sz[0]=0;
	dfs0(1,0);
	dfs1(1,0,1);
	for(int i=1;i<=n;++i){
		scanf("%d",&val[i]);
		chg(1,1,n,dfn[i],val[i]);
	}
	char ch[6];
	int q,ans;
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		std::cin>>ch+1;
		scanf("%d%d",&u,&v);
		switch(ch[2]){
			case 'H':{
				val[u]=v;
				chg(1,1,n,dfn[u],v);
				break;
			}
			case 'S':{
				ans=0;
				while(tp[u]!=tp[v]){
					if(dep[tp[u]]<dep[tp[v]]){
						Swap(u,v);
					}
					ans+=qrySm(1,1,n,dfn[tp[u]],dfn[u]);
					u=fa[tp[u]];
				}
				if(dep[u]>dep[v]){
					Swap(u,v);
				}
				ans+=qrySm(1,1,n,dfn[u],dfn[v]);
				printf("%d\n",ans);
				break;
			}
			case 'M':{
				ans=-INF;
				while(tp[u]!=tp[v]){
					if(dep[tp[u]]<dep[tp[v]]){
						Swap(u,v);
					}
					ans=Max(ans,qryMx(1,1,n,dfn[tp[u]],dfn[u]));
					u=fa[tp[u]];
				}
				if(dep[u]>dep[v]){
					Swap(u,v);
				}
				ans=Max(ans,qryMx(1,1,n,dfn[u],dfn[v]));
				printf("%d\n",ans);
				break;
			}
		}
	}
} 

int main(){
	init();
	return 0;
}

lp3676 小清新数据结构题

仔细考虑这道题,我们可以将问题转化为「修改」和「换根」两个操作。
对于修改操作,我们知道,每个点的权值对且仅对它到根节点上的这一条链上的每个点的答案产生贡献。
我们不妨令以1为根的情况下的每个点的修改前子树权值和为\(a_{i}\),修改对权值的改变为\(dlt\),那么可以计算得:
$$ans’=\sum(a_{i}+dlt)^2=\sum a_{i}^2+2dlt\times a_{i}+dlt^2\times len$$
故而,我们只需要用树链剖分套线段树维护树上区间平方和即可。

接下来我们考虑换根操作。
我们假设根从1换到了\(x\),那么子树权值大小会发生改变的仅有这条路径经过的点。我们不妨令换根后它们的子树权值和为\(b_{i}\),并有1~x为这条路径构成的序列,则我们发现答案会做出如下变动:
$$ans’=ans-\sum_{i=x}^1 a_{i}^2+\sum_{i=x}^1 b_{i}^2$$
我们发现,路径上的相邻点的子树的并集构成了整棵树。这也就意味着:
$$a_{i}+b_{i+1}=a_{0}=b_{x}$$
于是我们可以依此得到:
$$ans’=ans-\sum_{i=x}^1 a_{i}^2+b_x^2+\sum_{i=x-1}^1 (a_{0}-a_{i+1})^2$$
$$ans’=ans-\sum_{i=x}^2 a_{i}^2+(len-1)\times a_{0}^2-2a_{0}\times\sum_{i=x-1}^1 a_{i+1}+\sum_{i=x}^2a_{i}^2$$
$$ans’=(len-1)a_0^2-2a_{0}\sum_{i=x}^2a_{i}$$
同样也可以用树链剖分套线段树维护树上区间和与区间平方和。
注意:树剖不要写挂,下传给重儿子的链顶应该是本节点的链顶。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
typedef long long ll;

inline char rdc() {
 	static char buf[10000000], *p = buf, *end = buf;
	if (p == end) end = buf + fread(p = buf, sizeof(char), 10000000, stdin);
	return *(p++);
}

inline int rd(){
	int RT=0,c,f=1;
	while(!isdigit(c=rdc())){if(c=='-'){f=-1;}}
	do{RT=RT*10+c-'0';}while(isdigit(c=rdc()));
	return RT*f;
}

struct ee{
	int v;
	int nxt;
}e[400005];
int h[200005],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}

int n,q;
ll val[200005],sm[200005];
int fa[200005],dep[200005],tp[200005],sn[200005],sz[200005];
int dfn[200005],loc[200005],cnt=0;

inline void dfs0(int X,int FA){
	dep[X]=dep[FA]+1;
	fa[X]=FA;
	sz[X]=1;
	sm[X]=val[X];
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
		sm[X]+=sm[e[i].v];
	}
}

inline void dfs1(int X,int TP){
	loc[dfn[X]=++cnt]=X;
	tp[X]=TP;
	if(sn[X]){
		dfs1(sn[X],TP);
		//这里下传的应该是TP而非X...
		//树剖写挂了,我SB 
	}
	Fv(i,X){
		if(e[i].v==fa[X]||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,e[i].v);
	}
}
#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
struct data{
	ll sm;
	ll sm2;
	ll lzy;
}tr[2000005];

inline void rnw(int X,int Len,ll K){
	tr[X].sm2+=(K*K*Len+tr[X].sm*K*2);
	tr[X].sm+=(Len*K);
	tr[X].lzy+=K;
}
inline void pshd(int X,int L,int R){
	rnw(LS,LLEN,tr[X].lzy),rnw(RS,RLEN,tr[X].lzy);
	tr[X].lzy=0;
}
inline void updt(int X){
	tr[X].sm=tr[LS].sm+tr[RS].sm;
	tr[X].sm2=tr[LS].sm2+tr[RS].sm2;
}
inline void chg(int X,int L,int R,int A,int B,int V){
	if(L>=A&&R<=B){
		rnw(X,LEN,V);
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		chg(LS,L,MID,A,B,V);
	}
	if(B>MID){
		chg(RS,MID+1,R,A,B,V);
	}
	updt(X);
}
inline ll qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm;
	}
	if(L>B||R<A||B<A){
		return 0;
	}
	pshd(X,L,R);
	return qrySm(LS,L,MID,A,B)+qrySm(RS,MID+1,R,A,B);
}
inline ll qrySm2(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm2;
	}
	if(L>B||R<A||B<A){
		return 0;
	}
	pshd(X,L,R);
	return qrySm2(LS,L,MID,A,B)+qrySm2(RS,MID+1,R,A,B);
}
inline void build(int X,int L,int R){
	if(L==R){
		tr[X].sm=sm[loc[L]];
		tr[X].sm2=tr[X].sm*tr[X].sm;
		return;
	}
	build(LS,L,MID);build(RS,MID+1,R);
	updt(X);
}

void init(){
	n=rd(),q=rd();
	int u,v;
	for(int i=1;i<n;++i){
		u=rd(),v=rd();
		add(u,v);
	}
	for(int i=1;i<=n;++i){
		val[i]=rd();
	}
	dfs0(1,0);
	dfs1(1,1);
	build(1,1,n);
	int op,x,y;
	ll ans,a0=sm[1],sma,len;
	for(int i=1;i<=q;++i){
		op=rd();
		if(op==1){
			x=rd(),y=rd();
			y-=val[x];
			val[x]+=y;
			a0+=y;
			while(x){
				chg(1,1,n,dfn[tp[x]],dfn[x],y);
				x=fa[tp[x]];
			}
		}else{
			x=rd();
			len=sma=ans=0;
			ans=qrySm2(1,1,n,1,n);
			while(tp[x]!=tp[1]){
				len+=dfn[x]-dfn[tp[x]]+1;
				sma+=qrySm(1,1,n,dfn[tp[x]],dfn[x]);
				x=fa[tp[x]];
			}
			len+=dfn[x]-dfn[1];
			sma+=qrySm(1,1,n,dfn[1]+1,dfn[x]);
			printf("%lld\n",ans+a0*(len*a0-2*sma));
		}
	}
}
int main(){
	init();
	return 0;
}

CF487E Tourists

众所周知,圆方树是用来处理图上点双相关问题的。
同时,点双又是一个和简单路径密切相关的东西。故而这一题我们可以考虑用圆方树来处理。
我们发现,如果两点之间有多条简单路径,那么它们一定处于同一个点双中。所以,我们可以把原图转化为圆方树,这样就可以用树链剖分套线段树来求解询问了。
但是题目要求要修改点权,这要怎么办呢?

一个直观的想法是暴力修改每个点周围相邻的方点。然而事实上如果出现了个菊花套菊花套菊花图的话显然是会严重TLE的。
我们考虑一种动态维护一个方点的点值的算法。我们尝试对每个方点开一个mulitiset,每当修改一个点的点权的时候就把旧的点权删去然后插入新的点权,并更新方点点值。
然而,如果每个修改的圆点周围都有很多的方点的话,这种做法仍然有TLE的风险。我们考虑对于每个圆点,只更新它的父亲方点。
它对它的儿子方点的贡献,则在询问的时候统计。
这样复杂度就对了。
这就使用了圆方树上树链剖分套线段树解决了这道题。

注意:
树链剖分中更新最大孩子的部分,这里是son!不是sz!调了我一个晚上!

#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<set>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

std::multiset<int> s[200005]; 

const int INF=2147483647;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}

struct ee{
	int v;
	int nxt;
}e[2000005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int *H,int U,int V){
	Eadd(H,U,V);
	Eadd(H,V,U);
}


int dfn[200005],lw[100005];
//注意数组大小。 
int nm,cnt=0;
int st[100005],tp=0;
inline void dfs0(int X){
	dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	Fv(h0,i,X){
		if(!dfn[e[i].v]){
			dfs0(e[i].v);
			lw[X]=Min(lw[X],lw[e[i].v]);
			if(lw[e[i].v]==dfn[X]){
				++nm;
				for(int j=0;j!=e[i].v;--tp){
					j=st[tp];
					add(h,nm,j);
				}
				add(h,X,nm);
			}
		}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
}
int fa[200005],sz[200005],dep[200005],son[200005],top[200005],loc[200005];
inline void dfs1(int X,int FA){
	fa[X]=FA,dep[X]=dep[FA]+1,sz[X]=1;
	Fv(h,i,X){
		if(e[i].v!=FA){
			dfs1(e[i].v,X);
			sz[X]+=sz[e[i].v];
			if(sz[son[X]]<sz[e[i].v]){
				son[X]=e[i].v;
				//这里是son!不是sz!调了我一个晚上! 
			}
		}
	}
}
inline void dfs2(int X,int FA,int TP){
	dfn[X]=++cnt,loc[cnt]=X,top[X]=TP;
	if(son[X]){
		dfs2(son[X],X,TP);
	}
	Fv(h,i,X){
		if(e[i].v!=FA&&e[i].v!=son[X]){
			dfs2(e[i].v,X,e[i].v);
		}
	}
}

int n,m,q;
int a[200005];

#define MID (L+R>>1)
#define LS (X<<1)
#define RS (X<<1|1)

int tr[600005];
inline void bld(int X,int L,int R){
	if(L==R){
		tr[X]=a[loc[L]];
//		记得逆哈希 
		return;
	}
	bld(LS,L,MID);
	bld(RS,MID+1,R);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline void chg(int X,int L,int R,int P,int V){
	if(L==R){
		tr[X]=V;
		return;
	}
	P<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline int qry(int X,int L,int R,int A,int B){
	if(A>R||L>B){
		return INF;
	}
	if(A<=L&&R<=B){
		return tr[X];
	}
	return Min(qry(LS,L,MID,A,B),qry(RS,MID+1,R,A,B));
}

void init(){
	scanf("%d%d%d",&n,&m,&q);
	nm=n;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(h0,u,v);
	}
	dfs0(1);
	dfs1(1,0);
	cnt=0;
	dfs2(1,0,1);
	for(int i=1;i<=n;++i){
		if(fa[i]){
			s[fa[i]].insert(a[i]);
		}
	}
	for(int i=n+1;i<=nm;++i){
		a[i]=*s[i].begin();
	}
	
	bld(1,1,nm);
	char ch[3];
	int x,y;
	int ans;
	
	for(int i=1;i<=q;++i){
		scanf("%s%d%d",ch,&x,&y);
		if(ch[0]=='C'){
			chg(1,1,nm,dfn[x],y);
			if(fa[x]){
				u=fa[x];
				s[u].erase(s[u].lower_bound(a[x]));
				s[u].insert(y);
				if(a[u]!=*s[u].begin()){
					a[u]=*s[u].begin();
					chg(1,1,nm,dfn[u],a[u]);
				}
			}
			a[x]=y;
		}else{
			ans=INF;
			while(top[x]!=top[y]){
				if(dep[top[x]]<dep[top[y]]){
					Swap(x,y);
				}
				ans=Min(ans,qry(1,1,nm,dfn[top[x]],dfn[x]));
				x=fa[top[x]];
			}
			if(dfn[x]>dfn[y]){
				Swap(x,y);
			}
			ans=Min(ans,qry(1,1,nm,dfn[x],dfn[y]));
			if(x>n){
				ans=Min(ans,a[fa[x]]);
			}
			printf("%d\n",ans);
		}
	} 
}

int main(){
	init();
	return 0;
}

lp2468 SDOI2010 粟粟的书架

简化题意。
有一个n*m的矩阵,q个询问,求问,在每个矩阵中最少取多少个数,使得和至少为h。
观察数据范围,我们惊讶地发现这一题不可避免地要做两次。
因为,n,m<=200显然不是用普通的数据结构可以维护的。我们考虑使用\(cnt_{i,j,k}\)表示大于k的数的数量,\(sm_{i,j,k}\)表示大于k的数的总和。然后二分这个k来求解即可。
对于n==1的情况,我们很容易可以想到维护一棵权值主席树。对于每一个询问,我们在两棵权值线段树上二分然后求差。

#include<iostream>
#include<cstdio>
#define MID ((L+R)>>1)
int n,m,q;
int b[205][205],cnt[205][205][1005],sm[205][205][1005];
//不需要开longlong!!!MLE警告!!! 

inline long long cntQry(int X1,int Y1,int X2,int Y2,int K){
    return cnt[X2][Y2][K]-cnt[X1-1][Y2][K]-cnt[X2][Y1-1][K]+cnt[X1-1][Y1-1][K];
}
inline long long smQry(int X1,int Y1,int X2,int Y2,int K){
    return sm[X2][Y2][K]-sm[X1-1][Y2][K]-sm[X2][Y1-1][K]+sm[X1-1][Y1-1][K];
}
inline void slv2(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%d",&b[i][j]);
        }
    }
    for(int k=0;k<=1000;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                cnt[i][j][k]=cnt[i-1][j][k]+cnt[i][j-1][k]-cnt[i-1][j-1][k]+(int)(b[i][j]>=k);
                sm[i][j][k]=sm[i-1][j][k]+sm[i][j-1][k]-sm[i-1][j-1][k]+(int)(b[i][j]>=k)*b[i][j];
            }
        }
    }
    long long l,r,mid,h,ans;
    int X1,X2,Y1,Y2;
    while(q--){
        l=0,r=1001,ans=-1;
        scanf("%d%d%d%d%lld",&X1,&Y1,&X2,&Y2,&h);
        while(l<=r){
            mid=(l+r)>>1,smQry(X1,Y1,X2,Y2,mid)>=h?(ans=mid,l=mid+1):r=mid-1;
        }
        (~ans)?(printf("%lld\n",cntQry(X1,Y1,X2,Y2,ans)-(smQry(X1,Y1,X2,Y2,ans)-h)/ans)):(puts("Poor QLW"));
    }
    
//	 对于同一个k可能有多个值,而可能只需要选取部分。 
}
const int MAXN2=10000005;
int a[MAXN2];
//数组大小别算错 
class ChairmanTree{
    private:
        class Node{
            public:
                int l;
                int r;
                int fa;
                int sz;
                int sm;
        };
        Node tr[MAXN2];
        int cnt,rt[MAXN2];
        inline void build(int LST,int &NW,int L,int R,int V){
            NW=++cnt;tr[NW].sz=tr[LST].sz+1;tr[NW].sm=tr[LST].sm+V;
            if(L==R){return;}
            MID>=V?(build(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(build(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
            //如果值小等于MID。那么就更新右边的值;否则更新左边的值。一定要注意判断V==MID时的情况。 
            //如果更新的是右边的值,那么就把右边的节点与上一个版本的右边的节点一并下传,并修改本节点的左节点;否则反之。 
        }
        //从根往下搜索。注意减去的应当是右节点的值。 
        inline int qry(int A,int B,int L,int R,int V){
            int RT=0;
            while(L<R){(tr[tr[B].r].sm-tr[tr[A].r].sm)>V?(L=MID+1,B=tr[B].r,A=tr[A].r):(RT+=tr[tr[B].r].sz-tr[tr[A].r].sz,V-=(tr[tr[B].r].sm-tr[tr[A].r].sm),R=MID,B=tr[B].l,A=tr[A].l);}
            //同理,对于等于的情况也应当特别注意。 
            return RT+(V+L-1)/(L);
            //剩下的部分应该全部由大小为R的这些东西,也就是当前点的值来处理掉。故而要加上(V+L-1)/(L)
        }
    public:
        inline void ADD(int VER,int X){
            build(rt[VER-1],rt[VER],1,1000,X);
        }
        inline int QUREY(int LVER,int RVER,int X){
            return qry(rt[LVER-1],rt[RVER],1,1000,X);
        }
        inline int SUM(int L,int R){
            return tr[rt[R]].sm-tr[rt[L-1]].sm;
        }
        inline void INIT(){
            cnt=0;
        }
};
ChairmanTree T;
inline void slv1(){
    T.INIT();
    for(int i=1;i<=m;++i){
        scanf("%d",&a[i]);
        T.ADD(i,a[i]);
    }
    int l,r,tmp,x;
    while(q--){
        scanf("%d%d%d%d%d",&tmp,&l,&tmp,&r,&x);
        if(T.SUM(l,r)<x){
            puts("Poor QLW");
            continue;
        }
        printf("%d\n",T.QUREY(l,r,x));
    }
}

void init(){
    scanf("%d%d%d",&n,&m,&q);
    n==1?slv1():slv2();
}

int main(){
    init();
    return 0;
} 

lp1110 ZJOI2007 报表统计

事实上对于第一类询问和第二类询问我们可以分别处理。
第二类询问的处理方法是非常显然的。由于只有插入而没有删除操作,因此,第二类询问的答案只会缩小、不会增大。
故而,我们对整个数列的值维护一个Splay,每一次插入一个新的数以后,用它和它的前驱与它和它的后继的差的绝对值来更新第二类的答案。
这可以用multiset来简易地实现。
对于第一类询问,我们发现,维护这个值其实并不是难点——用线段树或者平衡树都可以轻松实现。问题在于,如何在插入新的数之后保持这个值。
我们仔细思考,发现,对于任意一段区间来说,它对答案的贡献只有三个:这个区间的答案,这个区间的左端点和这个区间的右端点。
故而,我们建一棵线段树或者平衡树,维护这三个信息(个人认为线段树比较科学。)每一次修改则修改对应的节点,然后递归向上更新即可。
这样就做完了,个人觉得实现难度还是比较低的。

#include<iostream>
#include<cstdio>
#include<set>
#define LS (X<<1)
#define RS (X<<1|1)
#define MID ((L+R)>>1)
inline int Abs(int X){
	return X>0?X:-X;
}

inline int Min(int A,int B){
	return A<B?A:B;
}

std::multiset<int> st;
int ansS=0x3f3f3f3f;
int n,m,a[500005];

class SegmentTree{
	private:
		class Node{
			public:
				int l;
				int r;
				int dlt;
			inline Node(){
				dlt=0x3f3f3f3f;
			}
			inline void init(int V){
				l=r=V;
			}
			inline void psh(int V){
				dlt=Min(dlt,Abs(r-V));
				r=V;
			}
		};
		Node tr[1100000];
		inline void updt(int X){
			tr[X].l=tr[LS].l;
			tr[X].r=tr[RS].r;
			tr[X].dlt=Min(Min(tr[LS].dlt,tr[RS].dlt),Abs(tr[LS].r-tr[RS].l));
		}
		inline void build(int L,int R,int X){
			if(L>R){
				return;
			}
			if(L==R){
				tr[X].init(a[L]);
				return;
			}
			build(L,MID,LS),build(MID+1,R,RS);
			updt(X);
		}
		inline void push(int L,int R,int X,int A,int V){
			if(L>R){
				return;
			}
			if(L==R){
				tr[X].psh(V);
				return;
			}
			A>MID?push(MID+1,R,RS,A,V):push(L,MID,LS,A,V);
			updt(X);
		}
		inline void prnt(int L,int R,int X){
			if(L>R){
				return;
			}
			if(L==R){
				printf("%d:[%d,%d,%d] ",X,tr[X].l,tr[X].r,tr[X].dlt);
				return;
			}
			prnt(L,MID,LS),prnt(MID+1,R,RS);
		}
	public:
		inline void PUSH(int X,int K){
			push(1,n,1,X,K);
		}
		inline void BUILD(){
			build(1,n,1);
		}
		inline int QUERYG(){
			return tr[1].dlt;
		}
		inline void PRINT(){
			prnt(1,n,1);
			puts("");
		}
};

inline void STPUSH(int K){
	st.insert(K);
	std::multiset<int> ::iterator it=st.find(K);
	int ans1,ans2;
	++it;
	if(it!=st.end()){
		ans1=*it;
	}else{
		ans1=0x3f3f3f3f;
	}
	--it;
	if(it!=st.begin()){
		--it;
		ans2=*it;
	}else{
		ans2=0x3f3f3f3f;
	}
	ans1=Abs(K-ans1),ans2=Abs(K-ans2);
	ansS=Min(ansS,Min(ans1,ans2));
}

SegmentTree T;
void init(){
	scanf("%d%d",&n,&m);
	int x;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		STPUSH(a[i]);
	}
	T.BUILD();
	char op[10];
	int k;
	for(int i=1;i<=m;++i){
		std::cin>>op;
		switch(op[4]){
			case 'R':{
				scanf("%d%d",&x,&k);
				T.PUSH(x,k);
				STPUSH(k);
				break;
			}
			case 'G':{
				printf("%d\n",T.QUERYG());
				break;
			}
			case 'S':{
				printf("%d\n",ansS);
				break;
			}
			case 'P':{
				T.PRINT();
				break;
			}
		}
	}
}

int main(){
	init();
	return 0;
}

lp1486 NOI2004 郁闷的出纳员

(似乎很少看见权值线段树的做法的样子。但是权值线段树如果动态开点、大胆卡常的话,是可以跑得飞快的。)
首先看一下题面,发现值域很小,很容易就可以想到用权值线段树维护。
支持:单点加,区间清零,查询第k大的权值线段树。
当然这题有一些细节。
一:如果初始工资低于工资下限,那么这个人就不存在。
二:维护的是第\(k\)大的而非第\(k\)小的。
三:由于是严格小于工资下限,要注意边界的开闭性。最好将公式写出来。

#include<iostream>
#include<cstdio>
using namespace std;
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
#define MID ((L+R)>>1)
#define LLEN (MID-L+1)
#define RLEN (R-MID) 
//支持:单点加,区间清零,查询第k大的权值线段树。
int tr[2000005],cnt=0; 
inline void updt(int X){
	tr[X]=tr[LS]+tr[RS];
}
inline void pshd(int X,int L,int R){
	if(!tr[X]){
		tr[LS]=tr[RS]=0;
	}
}
inline void add(int X,int L,int R,int A){
	if(L==R){
		++tr[X];
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		add(LS,L,MID,A);
	}else{
		add(RS,MID+1,R,A);
	}
	updt(X);
}
inline void clr(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		cnt+=tr[X];
		tr[X]=0;
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		clr(LS,L,MID,A,B);
	}
	if(B>MID){
		clr(RS,MID+1,R,A,B);
	}
	updt(X);
}
inline int srch(int X,int L,int R,int K){
	if(L==R){
		return L;
	}
	pshd(X,L,R);
	if(tr[RS]<K){
		return srch(LS,L,MID,K-tr[RS]);
	}else{
		return srch(RS,MID+1,R,K);
	}
}
inline int qry(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		return tr[X];
	}
	pshd(X,L,R);
	int rt=0;
	if(A<=MID){
		rt+=qry(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qry(RS,MID+1,R,A,B);
	}
	updt(X);
	return rt;
}
//1 k 插入大小为k的点
//2 k 全部数加上k
//3 k 全部数减去k
//4 k 查询第k大的值 
int n,m,tg=0,k;
char op[4];
void init(){
	scanf("%d%d",&n,&m);
	--m;
	for(int i=1;i<=n;++i){
		cin>>op;
		scanf("%d",&k);
		if(op[0]=='I'){
			//注意大于与大等于。 
			if(k>m){
				add(1,1,300001,k+100001+tg);
			}
		}else if(op[0]=='A'){
			tg-=k; 
		}else if(op[0]=='S'){
			tg+=k;
			clr(1,1,300001,1,m+100001+tg);
		}else if(op[0]=='F'){
			if(qry(1,1,300001,1,300001)<k){
				puts("-1");
			}else{
				printf("%d\n",srch(1,1,300001,k)-100001-tg);
			}
		}
	}
	printf("%d",cnt);
}
int main(){
	init();
	return 0;
}

 

lp2572 SCOI2010 序列操作

操作要求:
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反,也就是说把所有的0变成1,把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
我们考虑维护线段树来处理这些询问。
考虑线段树的基本性质。线段树的特性决定了它能够\(O(nlogn)\)来处理各种能够\(O(1)\)合并两个子区间信息的信息。
上述询问中,总共有多少个1是很容易可以维护的。最大的问题在于维护“最多有多少个连续的1”
实际上,对于这里的每一种信息,我们都需要对称地维护它们——即,在维护1的信息的同时也要维护0的信息。这是操作\(2\)导致的。
我们考虑对于两种询问分别考虑。
首先是\(3\),这个很好维护,直接维护\(1\)的个数即可。合并的时候简单相加即可。
对于\(4\),第一个想到的肯定是可以维护区间的最长连续1。
但是我们发现,仅仅维护这个信息还是不够的。因为这样是无法把子区间的信息合并的。
我们反过来考虑,对于一个区间,它的最长连续1有可能怎样从两个子区间转移过来。
首先,可能是完全被包含在两个区间之一。这种情况的话,只需要维护区间的最长连续1,然后取Max即可。
但是,还有可能这个区间是跨越了两个区间的。这时候我们需要维护,子区间左起最长连续1与右起最长连续1。
然后,在转移区间信息的时候,我们只需要再考虑两个子区间的左起最长连续1与右起最长连续1即可。
接着我们考虑对于端点起最长连续1的转移——这种转移存在一种特殊情况,也就是,这个区间的端点起最长连续1的长度超过了中点。
这时候需要特殊判定。
这样就做完了。
写了5k,的确是一道麻题。

另,我莫名其妙RE了,估计是不知道哪里边界判挂了。考试的时候要注意在不MLE的情况下多开几倍的数组保险。

#include<iostream>
#include<cstdio>

#define LS (X<<1)
#define RS (X<<1|1)
#define MID ((L+R)>>1)
#define LEN (R-L+1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
int n,m,a[100005],A,B,op;
inline int Max(int AA,int BB){
    return AA>BB?AA:BB;
}
struct data{ 
    int sm0;int sm1;
    int mx0;int mx1;
    int lmx0;int lmx1;
    int rmx0;int rmx1;
    //有翻转标记为1,否则为0;没有赋值为-1,有为0或1; 
    int lzy;int st;
    data(int sm0=0,int sm1=0,int mx0=0,int mx1=0,int lmx0=0,int lmx1=0,int rmx0=0,int rmx1=0,int lzy=0,int st=-1):
        sm0(sm0),sm1(sm1),mx0(mx0),mx1(mx1),lmx0(lmx0),lmx1(lmx1),rmx0(rmx0),rmx1(rmx1),lzy(lzy),st(st){}
}tr[300005];//262144
inline data mrg(const data &X,const data &Y,const data BS){
    data RT;
    RT.mx0=Max(X.mx0,Y.mx0);
    RT.mx0=Max(RT.mx0,X.rmx0+Y.lmx0);
    RT.sm0=X.sm0+Y.sm0;
    //一个巧妙的技巧,如果存在1,那么肯定不是全0,反之亦然。 
    RT.lmx0=X.sm1?X.lmx0:X.lmx0+Y.lmx0;
    RT.rmx0=Y.sm1?Y.rmx0:Y.rmx0+X.rmx0;
    
    RT.mx1=Max(X.mx1,Y.mx1);
    RT.mx1=Max(RT.mx1,X.rmx1+Y.lmx1);
    RT.sm1=X.sm1+Y.sm1;
    RT.lmx1=X.sm0?X.lmx1:X.lmx1+Y.lmx1;
    RT.rmx1=Y.sm0?Y.rmx1:Y.rmx1+X.rmx1;
    RT.lzy=BS.lzy;RT.st=BS.st;
    return RT;
}
inline void updt(int X){
    tr[X]=mrg(tr[LS],tr[RS],tr[X]);
}
inline void rnw1(int X,int L,int R){
    std::swap(tr[X].lmx0,tr[X].lmx1);
    std::swap(tr[X].rmx0,tr[X].rmx1);
    std::swap(tr[X].mx0,tr[X].mx1);
    std::swap(tr[X].sm0,tr[X].sm1);
}
inline void rnw20(int X,int L,int R){
    tr[X].lmx0=LEN;tr[X].lmx1=0;
    tr[X].rmx0=LEN;tr[X].rmx1=0;
    tr[X].mx0=LEN;tr[X].mx1=0;
    tr[X].sm0=LEN;tr[X].sm1=0;
}
inline void rnw21(int X,int L,int R){
    tr[X].lmx0=0;tr[X].lmx1=LEN;
    tr[X].rmx0=0;tr[X].rmx1=LEN;
    tr[X].mx0=0;tr[X].mx1=LEN;
    tr[X].sm0=0;tr[X].sm1=LEN;
}
inline void rnw(int X,int L,int R,int TYP){
    if(TYP==0){
        tr[X].lzy=0;tr[X].st=0;
        rnw20(X,L,R);
    }else if(TYP==1){
        tr[X].lzy=0;tr[X].st=1;
        rnw21(X,L,R);
    }else{
        tr[X].lzy^=1;
        rnw1(X,L,R);
    }
}
inline void pshd(int X,int L,int R){
    if(tr[X].st>-1){
        rnw(LS,L,MID,tr[X].st);rnw(RS,MID+1,R,tr[X].st);
        tr[X].st=-1;
    }
    if(tr[X].lzy){
        rnw(LS,L,MID,2);rnw(RS,MID+1,R,2);
        tr[X].lzy=0;
    }
}
inline void chg(int X,int L,int R,int TYP){
    if(A<=L&&R<=B){
        //如果完全被包含则直接更新。 
        rnw(X,L,R,TYP);
        return;
    }
    pshd(X,L,R);
    if(A<=MID){
        chg(LS,L,MID,TYP);
    }
    if(B>MID){
        chg(RS,MID+1,R,TYP);
    }
    updt(X);
}
inline data qry(int X,int L,int R){
    if(A<=L&&R<=B){
        pshd(X,L,R);
        return tr[X];
    }
    pshd(X,L,R);
    if(A<=MID){
        if(B>MID){
            return mrg(qry(LS,L,MID),qry(RS,MID+1,R),data());
        }else{
            return qry(LS,L,MID);
        }
    }else{
        if(B>MID){
            return qry(RS,MID+1,R);
        }else{
            return data();
        }
    }
}

inline void build(int X,int L,int R){
    if(L==R){
        tr[X]=(data){a[L]^1,a[L],a[L]^1,a[L],a[L]^1,a[L],a[L]^1,a[L],0,-1};
        return;
    }
    build(LS,L,MID);
    build(RS,MID+1,R);
    updt(X);
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    data ans;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&op,&A,&B);
        ++A,++B;
        if(op<3){
            chg(1,1,n,op);
        }else if(op==3||op==4){
            ans=qry(1,1,n);
            if(op==3){
                printf("%d\n",ans.sm1);
            }else if(op==4){
                printf("%d\n",ans.mx1);
            }
        }
    }
}
int main(){
    init();
    return 0;
}

 

lp1471 方差

大力上一个线段树。
将方差展开为由区间平方的和与区间和两项构成的多项式,然后维护区间平方的和与区间和。
具体来说,通过将二项式展开可以得到公式:
$$ \sum_{i=l}^{r}(a_{i}+k)^2=\sum_{i=l}^{r}a_{i}^2+\sum_{i=l}^{r}*k*2+(r-l+1)*k^2 $$
套用这个公式,就可以用与维护普通的线段树相似的方法来维护这个数据结构。

#include<iostream>
#include<cstdio>
using namespace std;
#define LEN (R-L+1)
#define MID ((L+R)>>1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
#define LS (X<<1)
#define RS (X<<1|1)
struct data{
	double sm;
	double sm2;
	double lzy;
}tr[270005];//262141
inline void rnw(int X,int Len,double K){
	tr[X].sm2+=(tr[X].sm*2*K+K*K*Len);
	tr[X].sm+=(K*Len);
	tr[X].lzy+=K;
}
inline void pshd(int X,int L,int R){
	rnw(LS,LLEN,tr[X].lzy);rnw(RS,RLEN,tr[X].lzy);
	tr[X].lzy=0;
}
inline void updt(int X){
	tr[X].sm2=tr[LS].sm2+tr[RS].sm2;
	tr[X].sm=tr[LS].sm+tr[RS].sm;
}
inline void add(int X,int L,int R,int A,int B,double K){
	if(L>=A&&R<=B){
		rnw(X,LEN,K);
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		add(LS,L,MID,A,B,K);
	}
	if(B>MID){
		add(RS,MID+1,R,A,B,K);
	}
	updt(X);
}
inline double qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm;
	}
	pshd(X,L,R);
	double rt=0;
	if(A<=MID){
		rt+=qrySm(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qrySm(RS,MID+1,R,A,B);
	}
	return rt;
}
inline double qrySm2(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm2;
	}
	pshd(X,L,R);
	double rt=0;
	if(A<=MID){
		rt+=qrySm2(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qrySm2(RS,MID+1,R,A,B);
	}
	return rt;
}
int n,m;
double a[100005];
inline void build(int X,int L,int R){
	if(L==R){
		tr[X].sm=a[L];
		tr[X].sm2=a[L]*a[R];
		return;
	}
	build(LS,L,MID);build(RS,MID+1,R);
	updt(X);
}
void init(){
	scanf("%d%d",&n,&m);
	double x;
	for(int i=1;i<=n;++i){
		scanf("%lf",a+i);
	}
	build(1,1,n);
	int op,l,r;
	while(m--){
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			scanf("%lf",&x);
			add(1,1,n,l,r,x);
		}else if(op==2){
			printf("%.4lf\n",qrySm(1,1,n,l,r)/(r-l+1));
		}else{
			x=qrySm(1,1,n,l,r);
			printf("%.4lf\n",(qrySm2(1,1,n,l,r)-x*x/(r-l+1))/(r-l+1));
		}
	}
}
int main(){
	init();
	return 0;
}