80,RE两个,help!
查看原帖
80,RE两个,help!
618344
powehi1楼主2022/5/20 15:33
#include<bits/stdc++.h>
using namespace std;
#define ul u<<1
#define ur u<<1|1
#define ll long long 
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
const int N=1e6+5;
int  n,m,p;
struct Node
{
    int l,r;
    ll sum;     
} t[N*8], tt[N*8];   // t--行  tt--列
void pushupc(int u)	  //  c--行  d--列 下面同理
{
    t[u].sum=t[ul].sum+t[ur].sum;
}
void pushupd(int u)
{
    tt[u].sum=tt[ul].sum+tt[ur].sum;
}
void build(int u,int l,int r)
{
    t[u].l=l,t[u].r=r;  tt[u].l=l,tt[u].r=r;
    if(l==r)
    {
        t[u].sum=tt[u].sum=0;  return ;
    }
    int mid=(l+r)>>1;
    build(ul,l,mid); build(ur,mid+1,r);
    pushupc(u); pushupd(u);
}
void modifyc(int u,int x) 
{
    if(t[u].l==x&&t[u].r==x) 
    {
        t[u].sum^=1;
        return ;
    }
    int mid=(t[u].l+t[u].r)>>1;
    if(x<=mid) modifyc(ul,x);
    if(x>mid)  modifyc(ur,x);
    pushupc(u);
}
void modifyd(int u,int x) 
{
    if(tt[u].l==x&&tt[u].r==x) 
    {
        tt[u].sum^=1;
        return ;
    }
    int mid=(tt[u].l+tt[u].r)>>1;
    if(x<=mid) modifyd(ul,x);
    if(x>mid)  modifyd(ur,x);
    pushupd(u);
}
ll queryc(int u,int l,int r)
{
    if(t[u].l>=l&&t[u].r<=r)    return t[u].sum;
    int mid=(t[u].l+t[u].r)>>1;
    ll sum=0;
    if(l<=mid) sum+=queryc(ul,l,r);
    if(r>mid)  sum+=queryc(ur,l,r);
    return sum;
}
ll queryd(int u,int l,int r)
{
    if(tt[u].l>=l&&tt[u].r<=r)  return tt[u].sum;
    int mid=(tt[u].l+tt[u].r)>>1;
    ll sum=0;
    if(l<=mid) sum+=queryd(ul,l,r);
    if(r>mid)  sum+=queryd(ur,l,r);
    return sum;
}
int main()
{
    cin>>n>>m>>p;
    build(1,1,n);
    int op,l,r;
    while(p--)
    {
        cin>>op;
        if(op==1)
        {
            cin>>l>>r;
            modifyc(1,l); modifyd(1,r);
        }
        if(op==2)
        {
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            ll k=queryc(1,x1,x2); ll kk=queryd(1,y1,y2);
            cout<<k*(y2-y1+1)+kk*(x2-x1+1)-2*k*kk<<endl;
        }
    }
}
2022/5/20 15:33
加载中...