首页 > 代码库 > AC日记——红色的幻想乡 洛谷 P3801

AC日记——红色的幻想乡 洛谷 P3801

红色的幻想乡

 

思路:

  线段树+容斥原理;

 

代码:

#include <bits/stdc++.h>using namespace std;#define maxn 100005#define maxm maxn<<2#define ll long longclass TreeType {    private:        int L[maxm],R[maxm],mid[maxm],dis[maxm];    public:        void build(int now,int l,int r)        {            L[now]=l,R[now]=r,dis[now]=0;            if(l==r) return;mid[now]=l+r>>1;            build(now<<1,l,mid[now]),build(now<<1|1,mid[now]+1,r);        }        void updata(int now,int to)        {            if(L[now]==R[now])            {                dis[now]^=1;                return;            }            if(to<=mid[now]) updata(now<<1,to);            else updata(now<<1|1,to);            dis[now]=dis[now<<1]+dis[now<<1|1];        }        int query(int now,int l,int r)        {            if(L[now]>=l&&R[now]<=r) return dis[now];            int res=0;            if(l<=mid[now]) res+=query(now<<1,l,r);            if(r>mid[now]) res+=query(now<<1|1,l,r);            return res;        }};struct TreeType tree1,tree2;int n,m,q;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();    }}int main(){    in(n),in(m),in(q);    tree1.build(1,1,n);    tree2.build(1,1,m);    int op,x1,y1,x2,y2;    while(q--)    {        in(op),in(x1),in(y1);        if(op==1) tree1.updata(1,x1),tree2.updata(1,y1);        else        {            in(x2),in(y2);            ll ans1=tree1.query(1,x1,x2),ans2=tree2.query(1,y1,y2);            printf("%lld\n",ans1*(y2-y1+1)+ans2*(x2-x1+1)-ans1*ans2*2);        }    }    return 0;}

 

AC日记——红色的幻想乡 洛谷 P3801