Submission #74886991

---

Source Code Expand

#include<bits/stdc++.h>

// #define XAERIC666
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#ifndef XAERIC666
  #define xaeric(...) {fprintf(stderr,__VA_ARGS__);fflush(stderr);}
#else
  #define xaeric(...) 114514
#endif
int read(){
  int x=0,f=1;
  char c=getchar();
  while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
  while('0'<=c&&c<='9'){x=x*10+c-48;c=getchar();}
  return x*f;
}
// void in(int*a,int n){for(int i=1;i<=n;i++)a[i]=read();}
// void out(int*a,int n){for(int i=1;i<=n;i++)printf("%lld%c",a[i]," \n"[i==n]);}
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _rep(i,a,b) for(int i=(b);i>=(a);--i)
#define YES puts("YES");
#define NO puts("NO");
void chmax(auto&a,auto b){if(a<b)a=b;}
void chmin(auto&a,auto b){if(a<b)a=b;}
using namespace std;

const int P=998244353;
const int N=2e5+5,D=25*N;

int n,m,a[N],t[D],tot,ls[D],rs[D],rt[N];
int bld(int cl,int cr){
  int u=++tot;
  if(cl>=cr){
    t[u]=a[cl];
    return u;
  }
  int mid=(cl+cr)/2;
  ls[u]=bld(cl,mid);
  rs[u]=bld(mid+1,cr);
  return u;
}
int cln(int u){
  ++tot;
  t[tot]=t[u];
  ls[tot]=ls[u];
  rs[tot]=rs[u];
  return tot;
}
int chg(int u,int cl,int cr,int p,int x){
  u=cln(u);
  if(cl>=cr){
    t[u]=x;
    return u;
  }
  int mid=(cl+cr)/2;
  if(p<=mid){
    ls[u]=chg(ls[u],cl,mid,p,x);
  }
  else{
    rs[u]=chg(rs[u],mid+1,cr,p,x);
  }
  t[u]=t[ls[u]]+t[rs[u]];
  return u;
}
// int qry(int u,int cl,int cr,int p){
//   if(cl>=cr){
//     return t[u];
//   }
//   int mid=(cl+cr)/2;
//   if(p<=mid){
//     return qry(ls[u],cl,mid,p);
//   }
//   return qry(rs[u],mid+1,cr,p);
// }
int qry(int u,int cl,int cr,int l,int r){
  if(l<=cl&&cr<=r){
    return t[u];
  }
  if(cr<l||r<cl){
    return 0;
  }
  int mid=(cl+cr)/2;
  return qry(ls[u],cl,mid,l,r)+qry(rs[u],mid+1,cr,l,r);
}
int q,cur[N];
void solve(){
  n=read(),m=read(),q=read();
  rt[0]=bld(1,m);
  for(int i=1;i<=n;i++){
    cur[i]=rt[0];
  }
  for(int i=1;i<=q;i++){
    int op=read();
    if(op==1){
      int x=read(),y=read();
      cur[x]=cur[y];
    }
    else if(op==2){
      int x=read(),y=read(),z=read();
      cur[x]=chg(cur[x],1,m,y,z);
    }
    else{
      int x=read(),l=read(),r=read();
      printf("%lld\n",qry(cur[x],1,m,l,r));
    }
  }
}

signed main(){
  int TTTT=1;
  // int TTTT=read();
  while(TTTT--){
    solve();
  }
}

Submission Info

Judge Result