洛谷題目傳送門
你谷無題解于是來補一發
随便百度題解,發現了不少諸如樹剖\(log^3\)LCT\(log^2\)的可怕描述。。。。。。
于是來想想怎麼利用題目的性質,把複雜度降下來。
首先,每個點的輸出狀态隻有\(0/1\),于是每個點的總狀态也非常有限,可以根據權值為\(1\)的兒子數量\(0-3\)分為四種,記為該點的點權。
我們都會模拟暴力過程——先改葉子節點(先預設為\(0\)改為\(1\)),如果它的父親此時權值為\(1\)的兒子數量從原來小于\(0\)的變成大于\(0\)的,那麼父親的權值也要改。以此類推,直到有一個節點輸出狀态沒有變化,那麼它的所有祖先肯定不會變。
通過模拟我們發現,每次修改的一定是一段自底向上的連續區間!
接着也就不難想到,隻有當點權為\(1\)時,才能通過修改點權變成\(2\),使輸出由\(0\)變成\(1\),進而繼續引發祖先的變化。那麼我們需要知道的就是,對于每一個葉子節點,它自底向上的連續一段點權為\(1\)的部分。
再讨論葉子節點\(1\)改\(0\)的情況,同理也可以發現我們還要維護自底向上的連續一段點權為\(2\)的部分。
這個可以樹剖(有很多元護法,都是\(log^2\)的,跳鍊和鍊修改都有\(log\))正在學樹剖,先留個坑,到時候再補。。。
當然可以LCT,講兩個維護法。第一種是用bool值維護區間是否有權值不為\(1/2\)的點,每次Splay上二分查找最深的不為\(1/2\)的點,把它伸展上來,右子樹做區間修改,這個點做單點修改。
因為寫二分比較麻煩(其實就是幾行的事),是以還不如直接維護最深的不為\(1/2\)點的編号,找都不用找。直接把它伸展上來。修改同上。容易發現這裡的LCT連換根都不要。
兩種寫法都需要注意特判:如果整條從根到葉子的鍊沒有一個不為\(1/2\)的點,直接做區間修改。
分享一個naive的錯誤——蒟蒻預設父節點的編号比子節點小,然後pushup直接取\(\max\),竟然獲得了95分?!調了半天本機對拍又是全AC(自己的資料生成器肯定是父節點的編号比子節點小啦。。。)
剛掉這題後還收獲了一點小經驗——不要給LCT永久化地貼上常數大的标簽!因為少一個\(log\),是以\(n\)越大越有優勢(這題\(5*10^5\)),還不用reverse。看看統計,就知道什麼叫LCT全方位(時間、空間、碼量)完爆樹剖的感覺了哈哈哈哈hhhh
https://www.luogu.org/recordnew/lists?uid=&pid=P4332&status=&sort=1
https://loj.ac/problem/2187/statistics/fastest
#include<cstdio>
#include<algorithm>
#define RG register
#define I inline
#define R RG int
#define lc c[x][0]
#define rc c[x][1]
#define G if(++ip==ie)if(fread(ip=ibuf,1,L,stdin))
using namespace std;
const int N=5e5+9,M=1.5e6+9,L=1<<19;
char ibuf[L],*ie=ibuf+L,*ip=ie-1;
int n,f[M],c[N][2],t[N],n1[N],n2[N],v[M],q[M],d[N];
I int max(R x,R y){return x>y?x:y;}
I int in(){
G;while(*ip<'-')G;
R x=*ip&15;G;
while(*ip>'-'){(x*=10)+=*ip&15;G;}
return x;
}
I bool nrt(R x){
return c[f[x]][0]==x||c[f[x]][1]==x;
}
I void up(R x){//先右兒子再自己最後左兒子
if(!(n1[x]=n1[rc])&&!(n1[x]=x*(v[x]!=1)))n1[x]=n1[lc];
if(!(n2[x]=n2[rc])&&!(n2[x]=x*(v[x]!=2)))n2[x]=n2[lc];
}
I void dn(R x,R tg){//被區間修改的要麼都是1要麼都是2,直接反轉資訊
v[x]^=3;swap(n1[x],n2[x]);t[x]+=tg;
}
I void all(R x){
if(nrt(x))all(f[x]);
if(t[x])dn(lc,t[x]),dn(rc,t[x]),t[x]=0;
}
I void rot(R x){
R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
if(nrt(y))c[z][c[z][1]==y]=x;
f[f[f[c[c[x][!k]=y][k]=w]=y]=x]=z;up(y);
}
I void sp(R x){
all(x);
for(R y;nrt(x);rot(x))
if(nrt(y=f[x]))rot((c[f[y]][0]==y)^(c[y][0]==x)?x:y);
up(x);
}
I void ac(R x){
for(R y=0;x;sp(x),rc=y,up(y=x),x=f[x]);
}
int main(){
n=in();R he,tl=0,i,x,tp,nowrt;//nowrt全局記錄根的輸出,友善,減小常數
for(i=1;i<=n;++i)d[f[in()]=f[in()]=f[in()]=i]=3;
for(;i<=3*n+1;++i)v[q[++tl]=i]=in()<<1;
for(he=1;he<=tl;++he){//懶得dfs了,直接從下往上拓撲排序預處理
x=q[he];if(x<=n)up(x);
v[f[x]]+=v[x]>>1;
if(!--d[f[x]])q[++tl]=f[x];
}
nowrt=v[1]>>1;
for(R q=in();q;--q){
tp=(v[x=in()]^=2)-1;//記錄目前變化類型
ac(x=f[x]);sp(x);
if((~tp?n1:n2)[x]){
sp(x=(~tp?n1:n2)[x]);
dn(rc,tp),up(rc);
v[x]+=tp;up(x);
}
else dn(x,tp),up(x),nowrt^=1;//注意特判
putchar(nowrt|'0');putchar('\n');
}
return 0;
}