SHARE
TWEET

TWOARR Author

a guest Feb 17th, 2019 123 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  6. #define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
  7. #define ll long long int
  8. #define FF first
  9. #define SS second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define pii pair<int,int>
  13. #define pll pair<long long int,long long int>
  14. #define sd(x) scanf("%d",&x)
  15. #define slld(x) scanf("%lld",&x)
  16. #define pd(x) printf("%d\n",x)
  17. #define plld(x) printf("%lld\n",x)
  18. #define pss printf
  19. #define MOD 1000000007
  20. #define INF 1e18
  21. #define eps 0.00001
  22. #define endl '\n'
  23. #define debug(n1) cout<<n1<<endl
  24. const int N=200005;
  25.  
  26. int n,q;
  27. ll a[N];
  28. ll b[N];
  29. ll tree[4*N];
  30. int lazy[4*N];
  31. int ql[N];
  32. int aql[N],aqr[N];
  33. int root[N];
  34. int lft[5000000];
  35. int rgt[5000000];
  36. ll ptree[5000000];
  37. int cur=0;
  38.  
  39. ll pquery(int l,int r,int s,int e,int i)
  40. {
  41.     if(s>r||e<l)
  42.         return 0;
  43.     if(s>=l&&e<=r)
  44.         return ptree[i];
  45.     int mid=(s+e)>>1;
  46.     return (pquery(l,r,s,mid,lft[i])+pquery(l,r,mid+1,e,rgt[i]));
  47. }
  48.  
  49. void pupd(int l,int s,int e,int i,int x)
  50. {
  51.     if(s==e)
  52.     {
  53.         ptree[i]=x;
  54.         return;
  55.     }
  56.     int mid=(s+e)>>1;
  57.     if(l<=mid)
  58.     {
  59.         ptree[cur]=ptree[lft[i]];
  60.         lft[cur]=lft[lft[i]];
  61.         rgt[cur]=rgt[lft[i]];
  62.         lft[i]=cur++;
  63.         pupd(l,s,mid,lft[i],x);
  64.     }
  65.     else
  66.     {
  67.         ptree[cur]=ptree[rgt[i]];
  68.         lft[cur]=lft[rgt[i]];
  69.         rgt[cur]=rgt[rgt[i]];
  70.         rgt[i]=cur++;
  71.         pupd(l,mid+1,e,rgt[i],x);
  72.     }
  73.     ptree[i]=(ptree[lft[i]]+ptree[rgt[i]]);
  74. }
  75.  
  76. void buildpseg(int l,int r,int i)
  77. {
  78.     if(l==r)
  79.     {
  80.         ptree[i]=b[l];
  81.         return;
  82.     }
  83.     int mid=(l+r)>>1;
  84.     lft[i]=cur++;
  85.     rgt[i]=cur++;
  86.     buildpseg(l,mid,lft[i]);
  87.     buildpseg(mid+1,r,rgt[i]);
  88.     ptree[i]=ptree[lft[i]]+ptree[rgt[i]];
  89. }
  90.  
  91. void lazify(int s,int e,int i)
  92. {
  93.     if(lazy[i])
  94.     {
  95.         tree[i]=pquery(s-aql[lazy[i]]+ql[lazy[i]],e-aql[lazy[i]]+ql[lazy[i]],1,n,root[lazy[i]]);
  96.         if(s!=e)
  97.         {
  98.             lazy[2*i]=lazy[i];
  99.             lazy[2*i+1]=lazy[i];
  100.         }
  101.         lazy[i]=0;
  102.     }
  103. }
  104.  
  105. void aupd(int l,int r,int s,int e,int i,int in)
  106. {
  107.     lazify(s,e,i);
  108.     if(s>r||e<l)
  109.         return;
  110.     if(s>=l&&e<=r)
  111.     {
  112.         lazy[i]=in;
  113.         lazify(s,e,i);
  114.         return;
  115.     }
  116.     int mid=(s+e)>>1;
  117.     aupd(l,r,s,mid,2*i,in);
  118.     aupd(l,r,mid+1,e,2*i+1,in);
  119.     tree[i]=tree[2*i]+tree[2*i+1];
  120. }
  121.  
  122. ll aquery(int l,int r,int s,int e,int i)
  123. {
  124.     if(s>r||e<l)
  125.         return 0;
  126.     lazify(s,e,i);
  127.     if(s>=l&&e<=r)
  128.         return tree[i];
  129.     int mid=(s+e)>>1;
  130.     return (aquery(l,r,s,mid,2*i)+aquery(l,r,mid+1,e,2*i+1));
  131. }
  132.  
  133. void buildseg(int l,int r,int i)
  134. {
  135.     if(l==r)
  136.     {
  137.         tree[i]=a[l];
  138.         return;
  139.     }
  140.     int mid=(l+r)>>1;
  141.     buildseg(l,mid,2*i);
  142.     buildseg(mid+1,r,2*i+1);
  143.     tree[i]=tree[2*i]+tree[2*i+1];
  144. }
  145.  
  146. int main()
  147. {
  148.     SPEED;
  149.     cin>>n>>q;
  150.     for(int i=1;i<=n;i++)
  151.         cin>>a[i];
  152.     for(int i=1;i<=n;i++)
  153.         cin>>b[i];
  154.     buildseg(1,n,1);
  155.     root[0]=cur++;
  156.     buildpseg(1,n,root[0]);
  157.     for(int i=1;i<=q;i++)
  158.     {
  159.         root[i]=cur++;
  160.         ptree[root[i]]=ptree[root[i-1]];
  161.         lft[root[i]]=lft[root[i-1]];
  162.         rgt[root[i]]=rgt[root[i-1]];
  163.         int t;
  164.         cin>>t;
  165.         if(t==1)
  166.         {
  167.             int x,y;
  168.             cin>>x>>y;
  169.             // b[x]=y;
  170.             pupd(x,1,n,root[i],y);
  171.         }
  172.         else if(t==2)
  173.         {
  174.             cin>>aql[i]>>aqr[i]>>ql[i];
  175.             // for(int j=aql[i];j<=aqr[i];j++)
  176.             //  a[j]=b[ql[i]+j-aql[i]];
  177.             aupd(aql[i],aqr[i],1,n,1,i);
  178.         }
  179.         else
  180.         {
  181.             int l,r;
  182.             cin>>l>>r;
  183.             // for(int j=l;j<=r;j++)
  184.             //  summ+=a[j];
  185.             ll d=aquery(l,r,1,n,1);
  186.             cout<<d<<endl;
  187.         }
  188.     }
  189.     return 0;
  190. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top