QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#663798 | #9492. 树上简单求和 | jerry3128 | 0 | 0ms | 0kb | C++23 | 7.7kb | 2024-10-21 17:28:09 | 2024-10-21 17:28:10 |
Judging History
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%