davidwang's Blog

这就是线段树解决区间覆盖的一类毒瘤问题

自从xyz111在cf上出了那道线段树解决区间覆盖问题之后，这已经几乎成为了一种毒瘤算法，这道题可以说是有过之而无不及。首先我们考虑一个区间内有正有负，加完之后绝对值的和和三部分有关系1.有负数变成负数，2.由正数变成正数，3.有负数变成正数，前面两种非常好讨论，只有第三种有苦难。但是我们注意到第三种每个数字只会出现一次，所以就变成了区间覆盖的那一类问题，用区间覆盖线段树来解决，复杂度通过势能分析。

所以树链剖分之后随便搞一搞复杂度 $$ O(nlog^2n) $$

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch>'9' || ch<'0';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 100010;
int son[N],fa[N],d[N],p[N][20],q[N],w[N],v[N],a[N],top[N],vis[N];
int start[N],to[N<<1],next[N<<1],size[N],cnt;
inline void connect(int a,int b){
	to[++cnt]=b; next[cnt]=start[a]; start[a]=cnt;
}
int n,m;
struct node{
	int l,r;
	int vmax,num;
	LL sum,flag;
	inline int mid(){ return r+l>>1; }
	inline int len(){ return r-l+1; }
	inline void add(LL x){
		if (vmax!=0 && vmax+x>=0) printf("Wrong!!!\n");
		if (vmax!=0) vmax+=x;
		flag+=x;
		sum+=x*(len()-num-num);
	} 
}s[N<<2];
void init(){
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read(); m=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<n;i++){
		int x=read(),y=read();
		connect(x,y);
		connect(y,x);
	}
	int head=0,tail=1,u;
	q[1]=1; d[1]=1; fa[1]=0;
	while (head<tail){
		u=q[++head];
		for (int p=start[u];p;p=next[p]){
			int &v=to[p];
			if (d[v]) continue;
			d[v]=d[u]+1; fa[v]=u;
			q[++tail]=v;
		}
	}
	for (int i=n;i;i--){
		int x=q[i];
		size[x]++;
		size[fa[x]]+=size[x];
		if (size[son[fa[x]]]<size[x]) son[fa[x]]=x;
	}
	int now=0;			
	for (int i=1;i<=n;i++){
		int x=q[i];
		if (vis[x]) continue;
		for (int j=x;j;j=son[j]){
			top[j]=x;
			w[j]=++now;
			vis[j]=1;
			v[now]=a[j];
		}
	}
	for (int i=1;i<=n;i++) p[i][0]=fa[i];
	for (int j=1;j<20;j++)
		for (int i=1;i<=n;i++)
			p[i][j]=p[p[i][j-1]][j-1];
}
inline int lca(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	int j;
	while (d[x]>d[y]){
		for (j=1;d[p[x][j]]>=d[y];j++);
		x=p[x][j-1];
	}
	while (x!=y){
		for (j=1;p[x][j]!=p[y][j];j++);
		x=p[x][j-1],y=p[y][j-1];
	}
	return x;	
}
inline void push_down(int x){
	if (s[x].r>s[x].l && s[x].flag){
		s[x<<1].add(s[x].flag);
		s[x<<1|1].add(s[x].flag);
		s[x].flag=0;
	}
}
inline int gvmax(int x,int y){
	if (x>=0) return y;
	if (y>=0) return x;
	return x>y?x:y;
}
inline void push_up(int x){
	s[x].sum=s[x<<1].sum+s[x<<1|1].sum;
	s[x].num=s[x<<1].num+s[x<<1|1].num;
	s[x].vmax=gvmax(s[x<<1].vmax,s[x<<1|1].vmax);
}
inline void build(int i,int l,int r){
	s[i].l=l; s[i].r=r;
	s[i].flag=0;
	if (l==r){
		s[i].num=v[l]<0?1:0;
		s[i].vmax=min(0,v[l]);
		s[i].sum=abs(v[l]);
		return;
	}
	int m=l+r>>1;
	build(i<<1,l,m); build(i<<1|1,m+1,r);
	push_up(i);
}
inline LL query(int i,int l,int r){
	if (s[i].l==l && s[i].r==r){
		return s[i].sum;
	}
	push_down(i);
	int m=s[i].mid();
	LL ret;
	if (r<=m) ret=query(i<<1,l,r);
	else if (l>m) ret=query(i<<1|1,l,r);
	else ret=query(i<<1,l,m)+query(i<<1|1,m+1,r);
	push_up(i);
	return ret;
}
inline void dfs(int i,int d){
	if (s[i].vmax==0 || s[i].vmax+d<0){
		s[i].add(d);
		return;
	}
	if (s[i].l==s[i].r){
		s[i].sum=s[i].vmax+d;
		s[i].vmax=0;
		s[i].num=0;
		return;
	}
	push_down(i);
	dfs(i<<1,d); 
	dfs(i<<1|1,d);
	push_up(i);
}
inline void modify(int i,int l,int r,int d){
	if (s[i].l==l && s[i].r==r){
		dfs(i,d);
		return;
	}
	push_down(i);
	int m=s[i].mid();
	if (r<=m) modify(i<<1,l,r,d);
	else if (l>m) modify(i<<1|1,l,r,d);
	else modify(i<<1,l,m,d),modify(i<<1|1,m+1,r,d);
	push_up(i);
}
inline LL Query(int x,int y){
	LL ans=0;
	int u=lca(x,y);
	while (d[x]>d[u]){
		if (d[top[x]]>d[u]){
			ans+=query(1,w[top[x]],w[x]);
			x=fa[top[x]];
		}else{
			ans+=query(1,w[son[u]],w[x]);
			x=u;
		}
	}
	swap(x,y);
	while (d[x]>d[u]){
		if (d[top[x]]>d[u]){
			ans+=query(1,w[top[x]],w[x]);
			x=fa[top[x]];
		}else{
			ans+=query(1,w[son[u]],w[x]);
			x=u;
		}
	}
	ans+=query(1,w[u],w[u]);
	return ans;
}
inline void Modify(int x,int y,int D){
	int u=lca(x,y);
	while (d[x]>d[u]){
		if (d[top[x]]>d[u]){
			modify(1,w[top[x]],w[x],D);
			x=fa[top[x]];
		}else{
			modify(1,w[son[u]],w[x],D);
			x=u;
		}
	}
	swap(x,y);
	while (d[x]>d[u]){
		if (d[top[x]]>d[u]){
			modify(1,w[top[x]],w[x],D);
			x=fa[top[x]];
		}else{
			modify(1,w[son[u]],w[x],D);
			x=u;
		}
	}
	modify(1,w[u],w[u],D);
	return;
}
void work()
{
	build(1,1,n);
	for (int i=1;i<=m;i++){
		int op=read(),x=read(),y=read();
		if (op==2){
			printf("%lld\n",Query(x,y));
		}else{
			int d=read();
			Modify(x,y,d);
		}
	}
}
int main()
{
	init();
	work();
	return 0;
}