Re: Untitled

From Cobalt Panda, 4 Years ago, written in Plain Text, viewed 400 times. This paste is a reply to Untitled from Soiled Crow - view diff
URL http://axuhongbo.top/paste/view/8d026015 Embed
Download Paste or View Raw
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. #define ll long long int
  4. #define ls rt<<1
  5. #define rs rt<<1|1
  6. using namespace std;
  7. const int maxn=400100;
  8. struct node
  9. {
  10.     int sum,cnt;
  11. }tr[maxn];
  12. int lz[maxn];
  13. int b[maxn];
  14. void pushdown(int rt)
  15. {
  16.     if(lz[rt])
  17.     {
  18.         lz[ls]+=lz[rt];
  19.         lz[rs]+=lz[rt];
  20.         tr[ls].cnt-=lz[rt];
  21.         tr[rs].cnt-=lz[rt];
  22.         lz[rt]=0;
  23.     }
  24. }
  25. void pushup(int rt)
  26. {
  27.     tr[rt].cnt=min(tr[ls].cnt,tr[rs].cnt);
  28.     tr[rt].sum=tr[ls].sum+tr[rs].sum;
  29. }
  30. void build(int l,int r,int rt)
  31. {
  32.     lz[rt]=0;
  33.     if(l==r)
  34.     {
  35.         tr[rt].cnt=b[l];
  36.         tr[rt].sum=0;
  37.         return ;
  38.     }
  39.     int mid=(l+r)/2;
  40.     build(l,mid,ls);
  41.     build(mid+1,r,rs);
  42.     tr[rt].cnt=min(tr[ls].cnt,tr[rs].cnt);
  43.     tr[rt].sum=tr[ls].sum+tr[rs].sum;
  44. }
  45. void update(int L,int R,int l,int r,int rt)
  46. {
  47.  
  48.     if(L<=l&&r<=R)
  49.     {
  50.         tr[rt].cnt-=1;
  51.         lz[rt]+=1;
  52.         return ;
  53.     }
  54.     pushdown(rt);
  55.     int mid=(l+r)/2;
  56.     if(L<=mid) update(L,R,l,mid,ls);
  57.     if(R>mid) update(L,R,mid+1,r,rs);
  58.     pushup(rt);
  59. }
  60. void date(int l,int r,int rt)
  61. {
  62.     if(tr[rt].cnt!=0) return ;
  63.     if(l==r)
  64.     {
  65.         tr[rt].sum++;
  66.         tr[rt].cnt=b[l];
  67.         return ;
  68.     }
  69.     pushdown(rt);
  70.     int mid=(l+r)/2;
  71.     date(l,mid,ls);
  72.     date(mid+1,r,rs);
  73.     pushup(rt);
  74. }
  75. int query(int ql,int qr,int l,int r,int rt)
  76. {
  77.     if(ql<=l&&r<=qr)
  78.     {
  79.         return tr[rt].sum;
  80.     }
  81.     pushdown(rt);
  82.     int mid=(l+r)/2;
  83.     int ans=0;
  84.     if(mid>=ql) ans+=query(ql,qr,l,mid,ls);
  85.     if(mid<qr) ans+=query(ql,qr,mid+1,r,rs);
  86.     return ans;
  87. }
  88. int main()
  89. {
  90.     int n,m,x,y;
  91.     char c[10];
  92.     while(scanf("%d%d",&n,&m)!=EOF)
  93.     {
  94.         memset(tr,0,sizeof(tr));
  95.         for(int i=1;i<=n;i++)scanf("%d",&b[i]);
  96.         build(1,n,1);
  97.  
  98.         while(m--)
  99.         {
  100.             scanf("%s%d%d",c,&x,&y);
  101.             if(!strcmp(c,"add"))
  102.             {
  103.                 update(x,y,1,n,1);
  104.                 date(1,n,1);
  105.             }
  106.             else
  107.             {
  108.                 printf("%d\n",query(x,y,1,n,1));
  109.             }
  110.         }
  111.     }
  112. }
  113.  

Reply to "Re: Untitled"

Here you can reply to the paste above

captcha