[LNOI2014] LCA
乐子
笑点解析：单log疯狂卡常才卡过那两双log做法。
全局平衡二叉树解法。
考虑差分，然后挂扫描线。\(dep_{LCA(x,y)}\)实际上就是将\(x\)到根的节点权值加1，然后求\(y\)到根的节点的权值和。
然后就是全局平衡二叉树的板子，标记永久化写就好了。
应该会抽时间写一个全局平衡二叉树的学习笔记，会把这道题当做例题，所以这里就不多说了。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(register int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(register int i = s;i >= t; i -= p)
namespace IO{#ifdef LOCALFILE*Fin(fopen("in.in","r")),*Fout(fopen("out.out","w"));#elseFILE*Fin(stdin),*Fout(stdout);#endifclass qistream{static const size_t SIZE=1<<27,BLOCK=64;FILE*fp;char buf[SIZE];int p;public:qistream(FILE*_fp=stdin):fp(_fp),p(0){fread_unlocked(buf+p,1,SIZE-p,fp);}void flush(){memmove(buf,buf+p,SIZE-p),fread_unlocked(buf+SIZE-p,1,p,fp),p=0;}qistream&operator>>(char&str){str=getch();while(isspace(str))str=getch();return*this;}template<class T>qistream&operator>>(T&x){x=0;p+BLOCK>=SIZE?flush():void();bool flag=false;for(;!isdigit(buf[p]);++p)flag=buf[p]=='-';for(;isdigit(buf[p]);++p)x=x*10+buf[p]-'0';x=flag?-x:x;return*this;}char getch(){return buf[p++];}qistream&operator>>(char*str){char ch=getch();while(ch<=' ')ch=getch();for(int i=0;ch>' ';++i,ch=getch())str[i]=ch;return*this;}}qcin(Fin);class qostream{static const size_t SIZE=1<<27,BLOCK=64;FILE*fp;char buf[SIZE];int p;public:qostream(FILE*_fp=stdout):fp(_fp),p(0){}~qostream(){fwrite_unlocked(buf,1,p,fp);}void flush(){fwrite_unlocked(buf,1,p,fp),p=0;}template<class T>qostream&operator<<(T x){int len=0;p+BLOCK>=SIZE?flush():void();x<0?(x=-x,buf[p++]='-'):0;do buf[p+len]=x%10+'0',x/=10,++len;while(x);for(int i=0,j=len-1;i<j;++i,--j)swap(buf[p+i],buf[p+j]);p+=len;return*this;}qostream&operator<<(char x){putch(x);return*this;}void putch(char ch){p+BLOCK>=SIZE?flush():void();buf[p++]=ch;}qostream&operator<<(char*str){for(int i=0;str[i];++i)putch(str[i]);return*this;}}qcout(Fout);
}using namespace IO;
#define rint register int
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define vec vector
#define eb emplace_back
#define N 50001
#define mod 201314
__int128_t base = 1;
template<class T>
inline T Mod(T x){return x-mod*(base*x>>64);}
vec<int> e[N];
int n,m,cq;
int siz[N],son[N],fa[N],c[N],sc[N],ss[N],lc[N],rc[N],ans[N];
int tag[N],sum[N];
struct node{int id,x,z;bool sgn;}q[N<<1];
void dfs1(rint x){siz[x] = 1;for(int y:e[x]){if(y == fa[x]) continue;fa[y] = x;dfs1(y);siz[x] += siz[y];if(!son[x] || siz[son[x]] < siz[y]) son[x] = y;}
}
int buildc(rint ql,rint qr){rint l = ql,r = qr,pos = 0,len = (sc[qr] - sc[ql]);while(l <= r){rint mid = (l + r) >> 1;if(2*(sc[mid]-sc[ql]) <= len) pos = mid,l = mid + 1;else r = mid - 1;}rint x = c[pos];ss[x] = qr-ql;if(ql < pos) fa[lc[x] = buildc(ql,pos)] = x;if(pos + 1 < qr) fa[rc[x] = buildc(pos+1,qr)] = x;return x;
}
int build(rint x){rint y = x;do for(int v:e[y]) if(v ^ son[y]) fa[build(v)] = y; while(y = son[y]);y = 0;do c[y++] = x,sc[y] = sc[y-1] + siz[x] - siz[son[x]];while(x = son[x]);return buildc(0,y);
}
inline void upd(rint x){bool flag = true;rint val = 0;while(x){sum[x] += val;if(flag){tag[x]++;if(rc[x]) tag[rc[x]]--;val += 1 + ss[lc[x]];sum[x] -= ss[rc[x]];}flag = (x ^ lc[fa[x]]);if(flag && (x ^ rc[fa[x]])) val = 0;x = fa[x];}
}
inline int qry(rint x){rint res = 0,val = 0;bool flag = true;while(x){if(flag){res += sum[x] - sum[rc[x]];res -= ss[rc[x]]*tag[rc[x]];val += 1 + ss[lc[x]];}res += val*tag[x];flag = (x ^ lc[fa[x]]);if(flag && (x ^ rc[fa[x]])) val = 0;x = fa[x];}return res;
}
inline void solve(){base = (base<<64)/mod;qcin>>n>>m;rint f,l,r,x;rep(i,2,n,1){qcin>>f;f++;e[f].eb(i);}rep(i,1,m,1){qcin>>l>>r>>x;r++;x++;if(l) q[++cq] = {i,l,x,0};q[++cq] = {i,r,x,1};}dfs1(1);rep(i,1,n,1) fa[i] = 0;build(1);int now = 0;sort(q+1,q+1+cq,[](node x,node y){return x.x<y.x;});rep(i,1,cq,1){while(now < q[i].x) now++,upd(now);if(q[i].sgn) ans[q[i].id] += qry(q[i].z);else ans[q[i].id] -= qry(q[i].z);}rep(i,1,m,1) qcout<<Mod(ans[i])<<'\n';}
signed main(){// cin.tie(nullptr)->sync_with_stdio(false);solve();
}
