QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#663798#9492. 树上简单求和jerry31280 0ms0kbC++237.7kb2024-10-21 17:28:092024-10-21 17:28:10

Judging History

This is the latest submission verdict.

  • [2024-10-21 17:28:10]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
  • [2024-10-21 17:28:09]
  • Submitted

answer

//ayanami±£ÓÓ£¬¿ä¸ç±£ÓÓ£¬¹·Âè±£ÓÓ£¬MDR±£ÓÓ£¬ï±µ¶¹Ö±£ÓÓ£¬M99±£ÓÓ£¬¿Ëµù±£ÓÓ
#include<bits/stdc++.h>
using namespace std;
int p1=1000000,p2=0;
char buf[1000005],wb[1000005];
int gc() {
	if(p1>=1000000)fread(buf,1,1000000,stdin),p1=0;
	return buf[p1++];
}
#define gc getchar
#define Loli true
#define Kon xor true
long long getint() {
	long long ret=0,flag=1;
	char c=gc();
	while(c<'0'||c>'9') {
		if(c=='-')flag=-1;
		c=gc();
	}
	while(c<='9'&&c>='0') {
		ret=(ret<<3)+(ret<<1)+c-'0';
		c=gc();
	}
	return ret*flag;
}
void pc(char x) {
	if(p2>=1000000)fwrite(wb,1,1000000,stdout),p2=0;
	wb[p2++]=x;
}
void wrt(long long x) {
	if(x<0)pc('-'),x=-x;
	int c[24]= {0};
	if(!x)return pc('0'),void();
	while(x)c[++c[0]]=x%10,x/=10;
	while(c[0])pc(c[c[0]--]+'0');
}
int n,m,q,N;
namespace T{
	int tot,sta[200005];
	struct node{
		int ch[4],fa,pre,num[2],c,prec;
		long long val,laz,preval,prelaz,slaz;
		long long sval[2];
		long long pretag,pretagtag[2],ctag;
		long long ans,tans;
	}v[400005];
	bool isroot(int x){return v[v[x].fa].ch[0]!=x&&v[v[x].fa].ch[1]!=x;}
	void add_son(int x,int t,int y) {v[x].ch[t]=y,v[y].fa=x;}
	void push_up_compress(int rt){
		if(!rt)return;
		v[rt].pre=v[rt].ch[0]?(v[rt].prec=v[v[rt].ch[0]].prec,v[rt].prelaz=v[v[rt].ch[0]].prelaz,v[rt].preval=v[v[rt].ch[0]].preval,v[v[rt].ch[0]].pre):(v[rt].prec=v[rt].c,v[rt].prelaz=v[rt].laz,v[rt].preval=v[rt].val,rt);
		
		v[rt].num[0]=v[v[rt].ch[0]].num[0]+v[v[rt].ch[1]].num[0]+(v[rt].ch[2]!=0);
		v[rt].num[1]=v[v[rt].ch[0]].num[1]+v[v[rt].ch[1]].num[1]+(v[rt].ch[3]!=0);
		v[rt].sval[0]=v[v[rt].ch[0]].sval[0]+v[v[rt].ch[1]].sval[0]+v[v[rt].ch[2]].val;
		v[rt].sval[1]=v[v[rt].ch[0]].sval[1]+v[v[rt].ch[1]].sval[1]+v[v[rt].ch[3]].val;
		v[rt].slaz=v[v[rt].ch[0]].slaz+v[v[rt].ch[1]].slaz+v[rt].laz;
		
		v[rt].ans=v[v[rt].ch[0]].ans+v[v[rt].ch[1]].ans+v[v[rt].ch[2]].ans+v[v[rt].ch[3]].ans+v[rt].laz*v[rt].val;
		v[rt].tans=v[v[rt].ch[0]].tans+v[v[rt].ch[1]].tans+v[v[rt].ch[2]].ans+v[v[rt].ch[3]].ans+(v[v[rt].ch[0]].slaz+v[rt].laz)*(v[v[rt].ch[2]].val+v[v[rt].ch[3]].val+v[v[rt].ch[1]].sval[0]+v[v[rt].ch[1]].sval[1]);
	}
	void push_up_rake(int rt){
		if(!rt)return;
		v[rt].val=v[v[rt].ch[2]].preval;
		v[rt].laz=v[v[rt].ch[2]].prelaz;
		v[rt].ans=v[v[rt].ch[2]].ans;
		v[rt].sval[0]=v[v[rt].ch[2]].sval[0];
		v[rt].sval[1]=v[v[rt].ch[2]].sval[1];
	}
	void push_up(int rt){
		rt<=N?push_up_compress(rt):push_up_rake(rt);
	}
	void push_pretag(int rt,long long val){
		if(!rt)return;
		if(rt<=N){
			v[rt].prelaz+=val,v[rt].pretag+=val,v[rt].slaz+=val;
			v[rt].ans+=v[rt].preval*val,v[rt].tans+=(v[rt].sval[0]+v[rt].sval[1])*val;
			(v[rt].pre==rt)?v[rt].laz+=val:0;
		}else{
			v[rt].pretag+=val,v[rt].laz+=val;
			v[rt].ans+=v[rt].val*val,v[rt].tans+=(v[rt].sval[0]+v[rt].sval[1])*val;
		}
	}
	void push_pretagtag(int rt,long long val[2]){
		if(!rt)return;
		v[rt].pretagtag[0]+=val[0],v[rt].pretagtag[1]+=val[1];
		v[rt].ans+=v[rt].sval[0]*val[0]+v[rt].sval[1]*val[1];
		v[rt].tans+=v[rt].sval[0]*val[0]+v[rt].sval[1]*val[1];
	}
	void push_ctag(int rt){
		if(!rt)return;
		long long tal = (v[rt].laz+(v[rt].ch[0]?(v[rt].ctag?0:v[v[rt].ch[0]].slaz)+v[rt].pretag:0));
		long long tmp[2]={tal, tal};
		long long tnp[2]={v[rt].pretag, v[rt].pretag};
		push_pretag(v[rt].ch[2],tal);
		push_pretag(v[rt].ch[3],tal);
		push_pretagtag(v[rt].ch[0],tnp);
		push_pretagtag(v[rt].ch[1],tmp);
		v[rt].ctag=1,v[rt].slaz=0,v[rt].laz=0,v[rt].prelaz=0,v[rt].pretag=0,v[rt].ans=v[rt].tans;
	}
	void push_down_compress(int rt){
		if(v[rt].ctag)push_ctag(v[rt].ch[0]),push_ctag(v[rt].ch[1]),v[rt].ctag=0;
		if(v[rt].pretag)push_pretag(v[rt].ch[0],v[rt].pretag),v[rt].pretag=0;
		if(v[rt].pretagtag[0]||v[rt].pretagtag[1]){
			push_pretag(v[rt].ch[2],v[rt].pretagtag[0]);
			push_pretag(v[rt].ch[3],v[rt].pretagtag[1]);
			push_pretagtag(v[rt].ch[0],v[rt].pretagtag);
			push_pretagtag(v[rt].ch[1],v[rt].pretagtag);
			v[rt].pretagtag[0]=0,v[rt].pretagtag[1]=0;
		}
	}
	void push_down_rake(int rt){
		if(v[rt].pretag)push_pretag(v[rt].ch[2],v[rt].pretag),v[rt].pretag=0;
	}
	void push_down(int rt){
		rt<=N?push_down_compress(rt):push_down_rake(rt);
	}
	int son(int p,int x){
		if(v[p].ch[0]==x)return 0;
		if(v[p].ch[1]==x)return 1;
		if(v[p].ch[2]==x)return 2;
		if(v[p].ch[3]==x)return 3;
		puts("Error"),exit(233);
	}
	void rot(int x) {
		int p=v[x].fa,g=v[p].fa,d=(v[p].ch[1]==x);
		if(g)v[g].ch[son(g,p)]=x;
		v[x].fa=g,add_son(p,d,v[x].ch[!d]),add_son(x,!d,p);
		push_up(p),push_up(x);
	}
	void pre_push_down(int x) {
		if(!isroot(x))pre_push_down(v[x].fa);
		push_down(x);
	}
	void splay(int x) {
		pre_push_down(x);
		while(!isroot(x)) {
			int p=v[x].fa,g=v[p].fa;
			if(!isroot(p))rot(p==v[g].ch[0]^x==v[p].ch[0]?x:p);
			rot(x);
		}
		push_up(x);
	}
	void local_splay(int x,int d) {
		int goal=v[x].fa;
		push_down(x);
		while(v[x].ch[d])x=v[x].ch[d],push_down(x);
		while(!isroot(x)&&v[x].fa!=goal)rot(x);push_up(x);
	}
	void erase(int x){v[sta[++sta[0]]=x]=node();}
	int new_node(){return sta[0]?sta[sta[0]--]:++tot;}
	void ins(int x,int y){
		if(!y)return;
		int t=new_node();
		add_son(t,0,v[x].ch[2|v[y].prec]),add_son(t,2,y);
		push_up(t),v[x].ch[1]=0,add_son(x,2|v[y].prec,t),push_up(x);
	}
	void del(int x,int y){
		if(!y)return;
		splay(v[y].fa);int t=v[x].ch[2|v[y].prec];
		push_down(t),add_son(x,1,v[t].ch[2]);
		if(v[t].ch[0])local_splay(v[t].ch[0],1),add_son(v[t].ch[0],1,v[t].ch[1]),v[x].ch[2|v[y].prec]=v[t].ch[0];
		else push_down(v[t].ch[1]),v[x].ch[2|v[y].prec]=v[t].ch[1];
		erase(t),t=v[x].ch[2|v[y].prec],v[t].fa=x,push_up(t);
	}
	int access(int x){
		int y=x,ret=x,stot=0;
		static int s[200005];
		splay(s[++stot]=x),x=v[x].fa;
		for(;x;y=x,x=v[x].fa)
			splay(x),s[++stot]=x=v[x].fa,splay(x),push_up(ret=x);
		
		for(int i=stot;i>=1;i--){
			ins(s[i],v[s[i]].ch[1]),del(s[i],s[i-1]),push_up(s[i]),s[i-1]?splay(s[i-1]):void();
		}
		return ret;
	}
	void link(int x,int y){
		if(!y)return;
		access(x),splay(x),splay(y),add_son(x,1,y),push_up(x);
	}
}
int l[200005],r[200005],p[200005];
map<int,int> mp[200005];
set<int> lset[200005],rset[200005];
int main() {
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	n=getint(),m=getint(),q=getint(),T::tot=2*n-1,N=2*n-1;
	for(int i=1;i<=(n<<1)-1;i++){
		int ls=getint(),rs=getint();
		T::v[ls].c=0,T::v[rs].c=1,T::access(i),T::v[i].val=getint(),T::push_up(i),p[ls]=i,p[rs]=i;
		l[i]=getint(),r[i]=getint(),T::link(i,ls),T::link(i,rs);
		mp[l[i]][r[i]]=i,lset[l[i]].insert(r[i]),rset[r[i]].insert(l[i]);
	}
	for(int i=1;i<=m;i++){
		int L=getint(),R=getint();
		long long tag=getint();
		int lnode = mp[L][*--lset[L].upper_bound(R)];
		int rnode = mp[*  rset[R].lower_bound(L)][R];
		
		if(lnode == rnode){
			if(lnode == 1)T::access(1),T::v[1].laz+=tag,T::push_up(1);
			else T::access(p[lnode]),T::splay(p[lnode]),T::push_ctag(p[lnode]),T::push_down(p[lnode]),T::push_pretag(T::v[p[lnode]].ch[2|T::v[lnode].c],tag),T::push_up(p[lnode]);
		}else{
			int lca=(T::access(lnode),T::access(rnode));
			long long ltag[2]={0, tag}, rtag[2]={tag, 0}, iltag[2]={0, -tag}, irtag[2]={-tag, 0};
			if(T::v[lnode].c==0)T::access(lnode),T::splay(lnode),T::v[lnode].laz+=tag,T::push_up(lnode);
			if(T::v[rnode].c==1)T::access(rnode),T::splay(rnode),T::v[rnode].laz+=tag,T::push_up(rnode);
			lnode=p[lnode], rnode=p[rnode];
						
			T::access(lnode),T::splay(lnode),T::push_ctag(lnode),T::push_pretagtag(lnode,ltag),T::access(lca),T::splay(lca),T::push_pretagtag(lca,iltag);
			T::access(rnode),T::splay(rnode),T::push_ctag(rnode),T::push_pretagtag(rnode,rtag),T::access(lca),T::splay(lca),T::push_pretagtag(lca,irtag);
		}
		T::splay(1),wrt(T::v[1].ans),pc('\n');
	}
	fwrite(wb,1,p2,stdout);
	return Loli Kon;
}

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

3000 3000
7236742292501328495 17973811477309806363 16075782662531676171 17971236571771878676 11392080645527132110 3685563455925680459 9773593720088356683 8313828403245053795 7736401634567449043 1634817828009987181 6951124933529719486 12775126714635387213 15460977209223753216 397573676785925632 31372...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Test #21:

score: 0
Runtime Error

input:

200000 200000
622783158027686223 2242697872372232537 8481648430436878777 10092474834140799044 15403999682625301609 12614289513474949582 9180944589267018841 7823784919308285798 8257785171198951273 5134508521895120821 8041682272181381093 3835432206618893170 2653803171409877650 5589823419153460372 1007...

output:


result:


Subtask #5:

score: 0
Runtime Error

Test #27:

score: 0
Runtime Error

input:

200000 200000
1958469220619413759 14991498002015735322 6054491201406941902 18206143187746582567 15082377615826460430 2936248617457291604 10073577150351675920 16534472678586906457 2207599132486246393 10301540360769075442 1492580560381080472 551692353431379140 13238280352539145808 8462626987240986565 ...

output:


result:


Subtask #6:

score: 0
Runtime Error

Test #34:

score: 0
Runtime Error

input:

200000 200000
6794776813641982926 1561596256197101737 10910039723053043515 7892247858295192798 12233819960547881004 17695389034783066733 9173201689566865598 17626618141377486739 7358781671024283919 6787559733384974662 3884392438269280436 14872846228351316833 9037842441501571648 14299818404271084016 ...

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%