BZOJ 3779 LCT 线段树 DFS序坑-白红宇

BZOJ 3779 LCT 线段树 DFS序坑

阅读量：4678 次

发布时间：2019-06-09

本文共 8142 字，大约阅读时间需要 27 分钟。

hhhh抄了半天lty代码最后T了对拍也没事..

药丸

mine

#pragma GCC optimize("O3")//By SiriusRen#include 
     
      using namespace std;const int N=100500;typedef long long ll;int n,m,xx,yy,first[N],next[N*2],v[N*2],tot;int in[N],out[N],deep[N],p[N],f[N][19],cnt,lazy[N*4];int fa[N],ch[N][2],rev[N],q[N],top,root;ll sum[N*4];char op[10];void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}void dfs(int x){    in[x]=++cnt,p[cnt]=x;    for(int i=first[x];~i;i=next[i])if(!deep[v[i]])        deep[v[i]]=deep[x]+1,f[v[i]][0]=x,fa[v[i]]=x,dfs(v[i]);    out[x]=cnt;}int lca(int x,int y){    if(deep[x]
      
       =deep[y])x=f[x][i];    if(x==y)return x;    for(int i=16;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];    return f[x][0];}int _lca(int x,int y){
   for(int i=16;~i;i--)if(deep[f[x][i]]>deep[y])x=f[x][i];return x;}void pushup(int pos){sum[pos]=sum[pos<<1]+sum[pos<<1|1];}void pushdown(int l,int r,int pos){    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;    lazy[lson]+=lazy[pos],sum[lson]+=1ll*(mid-l+1)*lazy[pos];    lazy[rson]+=lazy[pos],sum[rson]+=1ll*(r-mid)*lazy[pos];    lazy[pos]=0;}void build(int l,int r,int pos){    if(l==r){sum[pos]=deep[p[l]];return;}    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;    build(l,mid,lson),build(mid+1,r,rson),pushup(pos);}void insert(int l,int r,int pos,int L,int R,int wei){    if(l>=L&&r<=R){lazy[pos]+=wei;sum[pos]+=1ll*wei*(r-l+1);return;}    if(lazy[pos])pushdown(l,r,pos);    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;    if(mid
       
        =R)insert(l,mid,lson,L,R,wei);    else insert(l,mid,lson,L,R,wei),insert(mid+1,r,rson,L,R,wei);    pushup(pos);}ll query(int l,int r,int pos,int L,int R){    if(l>=L&&r<=R)return sum[pos];    if(lazy[pos])pushdown(l,r,pos);    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;    if(mid
        
         =R)return query(l,mid,lson,L,R);    else return query(l,mid,lson,L,R)+query(mid+1,r,rson,L,R);}bool isroot(int x){
   return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}void rotate(int p){    int q=fa[p],y=fa[q],x=(ch[q][1]==p);    ch[q][x]=ch[p][!x],fa[ch[q][x]]=q;    ch[p][!x]=q,fa[p]=y;    if(!isroot(q)){        if(ch[y][1]==q)ch[y][1]=p;        if(ch[y][0]==q)ch[y][0]=p;    }fa[q]=p;}void push_down(int x){
   if(rev[x])rev[ch[x][0]]^=1,rev[ch[x][1]]^=1,swap(ch[x][0],ch[x][1]),rev[x]=0;}void Pushdown(int x){    q[++top]=x;    for(int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];    while(top)push_down(q[top]),top--;}void splay(int x){    Pushdown(x);    for(int y=fa[x];!isroot(x);rotate(x),y=fa[x])if(!isroot(y)){        if((ch[fa[y]][0]==y)^(ch[y][0]==x))rotate(x);        else rotate(y);    }}void find(int x,int y){    Pushdown(x);    while(ch[x][0])x=ch[x][0],Pushdown(x);    if(x==root)insert(1,n,1,1,n,y);    else if(lca(x,root)!=x)insert(1,n,1,in[x],out[x],y);    else{        int t1=_lca(root,x);        if(in[t1]^1)insert(1,n,1,1,in[t1]-1,y);        if(out[t1]^n)insert(1,n,1,out[t1]+1,n,y);    }}void access(int x){    for(int t=0;x;ch[x][1]=t,t=x,x=fa[x]){        splay(x);if(ch[x][1])find(ch[x][1],1);if(t)find(t,-1);    }}void makeroot(int x){access(x),splay(x),rev[x]^=1,root=x;}ll Query(int x,int k){    if(x==root)return k?n:query(1,n,1,1,n);    if(lca(x,root)!=x)return k?out[x]-in[x]+1:query(1,n,1,in[x],out[x]);    int t1=_lca(root,x);ll r=0;    if(in[t1]^1)r=k?in[t1]-1:query(1,n,1,1,in[t1]-1);    if(out[t1]^n)r+=k?n-out[t1]:query(1,n,1,out[t1]+1,n);    return r;}inline int read(){    int x=0;char p=getchar();    while(p<'0'||p>'9')p=getchar();    while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();    return x;}int main(){    memset(first,-1,sizeof(first));    scanf("%d%d",&n,&m);    for(int i=1;i

lty

#include 
     
      #include 
      
       #define M ((L+R)>>1)#define lc o<<1#define rc o<<1|1#define ls lc,L,M#define rs rc,M+1,R#define f(x) t[x].p#define l(x) t[x].s[0]#define r(x) t[x].s[1]#define LC(x) (r(f(x))==x)#define st(a,b,c) t[a].s[b]=c;f(c)=a typedef long long ll;const int N=100005,B=200005;char op[9]; int n,m,x,y,e,tt,sd,hd[N],nx[B],to[B],bg[N],ed[N],f[N][17],d[N],p[N],v[N*4]; ll sm[N*4];struct nd {
   int p,rv,s[2];}t[N];void ad(int x,int y) {to[++e]=y,nx[e]=hd[x],hd[x]=e;} void dfs(int x) {    bg[x]=++tt,p[tt]=x;    for(int i=hd[x];i;i=nx[i]) if(!d[to[i]]) d[to[i]]=d[x]+1,f[to[i]][0]=x,f(to[i])=x,dfs(to[i]);    ed[x]=tt;}int lca(int x,int y) {    if(d[x]
       
        =d[y]) x=f[x][i];    if(x==y) return x;    for(int i=16;~i;i--) if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];    return f[x][0];}int _lca(int x,int y) {
   for(int i=16;~i;i--) if(d[f[x][i]]>d[y]) x=f[x][i]; return x;}void pu(int o) {sm[o]=sm[lc]+sm[rc];}void bd(int o,int L,int R) {    if(L==R) {sm[o]=d[p[L]]; return;}    bd(ls),bd(rs),pu(o);}void PD(int o,int L,int R) {
   if(v[o]) v[lc]+=v[o],v[rc]+=v[o],sm[lc]+=(ll)(M-L+1)*v[o],sm[rc]+=(ll)(R-M)*v[o],v[o]=0;}void upd(int o,int L,int R,int l,int r,int x) {    if(l<=L&&r>=R) {v[o]+=x,sm[o]+=(ll)x*(R-L+1); return;}    PD(o,L,R);    if(l<=M) upd(ls,l,r,x); if(r>M) upd(rs,l,r,x);    pu(o);}ll qr(int o,int L,int R,int l,int r) {    if(l<=L&&r>=R) return sm[o];    PD(o,L,R);    if(r<=M) return qr(ls,l,r);    if(l>M) return qr(rs,l,r);    return qr(ls,l,r)+qr(rs,l,r);} bool rt(int x) {
   return l(f(x))!=x&&r(f(x))!=x;}void _pd(int x) {
   if(t[x].rv) t[l(x)].rv^=1,t[r(x)].rv^=1,std::swap(l(x),r(x)),t[x].rv=0;}void pd(int x) {
   if(!rt(x)) pd(f(x)); _pd(x);}void rot(int x) {
   int y=f(x),lx=LC(x); st(y,lx,t[x].s[!lx]); if(!rt(y)) st(f(y),LC(y),x); st(x,!lx,y);}void sp(int x) {pd(x); for(int y=f(x);!rt(x);rot(x),y=f(x)) if(!rt(y)) {
   if(LC(x)^LC(y)) rot(x); else rot(y);}}void fd(int x,int y) {    _pd(x);    while(l(x)) x=l(x),_pd(x);    if(x==sd) upd(1,1,n,1,n,y);    else if(lca(x,sd)^x) upd(1,1,n,bg[x],ed[x],y);    else {        int t1=_lca(sd,x);        if(bg[t1]^1) upd(1,1,n,1,bg[t1]-1,y);        if(ed[t1]^n) upd(1,1,n,ed[t1]+1,n,y);    }}void acs(int x) {    for(int y=0;x;r(x)=y,y=x,x=f(x)) {        sp(x);        if(r(x)) fd(r(x),1);        if(y)fd(y,-1);    }}void mk(int x) {acs(x),sp(x),t[x].rv^=1,sd=x;}ll qs(int x,int k) {    if(x==sd) return k?n:qr(1,1,n,1,n);    if(lca(x,sd)^x) return k?ed[x]-bg[x]+1:qr(1,1,n,bg[x],ed[x]);    int t1=_lca(sd,x); ll r=0;    if(bg[t1]^1) r=k?bg[t1]-1:qr(1,1,n,1,bg[t1]-1);    if(ed[t1]^n) r+=k?n-ed[t1]:qr(1,1,n,ed[t1]+1,n);    return r;} int main() {    scanf("%d%d",&n,&m);    for(int i=1;i

//By SiriusRen#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define rd (rand()|rand()<<15)int seed;const int mod=1000000007;int main(){    freopen("seed.txt","r",stdin);    scanf("%d",&seed);    srand(seed+time(0));    rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();    rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();    rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();    rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();    rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();rand();    freopen("seed.txt","w",stdout);    freopen("in.txt","w",stdout);    int n=100000,m=100000;    printf("%d %d\n",n,m);    for(int i=2;i<=n;i++)printf("%d %d\n",rand()%(i-1)+1,i);    for(int i=1;i<=m;i++){        int t=rand()%3;        if(t==0)printf("RELEASE %d\n",rand()%n+1);        else if(t==1)printf("RECENTER %d\n",rand()%n+1);        else printf("REQUEST %d\n",rand()%n+1);    }}

//By SiriusRen#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int cases,xx;int main(){    while(1){        printf("case # %d\n",++cases);        system("mk.exe");        long tim=clock();        system("a.exe
         
          out1.txt");        printf("programme a time=%ld\n",clock()-tim);        tim=clock();        system("b.exe
          
           out2.txt"); printf("programme b time=%ld\n",clock()-tim); if(system("fc out1.txt out2.txt")){ puts("Wrong Answer"); while(1); }printf("Accepted\n\n"); }}