首页 > 代码库 > AC日记——贪婪大陆 洛谷 P2184

AC日记——贪婪大陆 洛谷 P2184

贪婪大陆

 

思路;

  树状数组;

  跪烂。。

 

代码:

#include <bits/stdc++.h>using namespace std;#define maxn 100005int n,m,ltree[maxn],rtree[maxn],tot;inline void in(int &now){    char Cget=getchar();now=0;    while(Cget>9||Cget<0)Cget=getchar();    while(Cget>=0&&Cget<=9)    {        now=now*10+Cget-0;        Cget=getchar();    }}inline int lowbit(int x){    return x&(-x);}inline void add(int x,bool di){    if(di)    {        while(x<=n)        {            ltree[x]++;            x+=lowbit(x);        }    }    else    {        while(x<=n)        {            rtree[x]++;            x+=lowbit(x);        }    }}inline int sum(int l,int r,bool di){    l--;int res=0;    if(di)    {        while(r) res+=ltree[r],r-=lowbit(r);        while(l) res-=ltree[l],l-=lowbit(l);    }    else    {        while(r) res+=rtree[r],r-=lowbit(r);        while(l) res-=rtree[l],l-=lowbit(l);    }    return res;}int main(){    in(n),in(m);int q,l,r;    while(m--)    {        in(q),in(l),in(r);        if(q==1) tot++,add(l,true),add(r,false);        else        {            int res=tot;            if(l>1) res-=sum(1,l-1,false);            if(r<n) res-=sum(r+1,n,true);            printf("%d\n",res);        }    }    return 0;}

 

AC日记——贪婪大陆 洛谷 P2184