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

红色的幻想乡

思路:

  线段树+容斥原理;

代码:

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
#define maxm maxn<<2
#define ll long long
class 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]=;
if(l==r) return;mid[now]=l+r>>;
build(now<<,l,mid[now]),build(now<<|,mid[now]+,r);
}
void updata(int now,int to)
{
if(L[now]==R[now])
{
dis[now]^=;
return;
}
if(to<=mid[now]) updata(now<<,to);
else updata(now<<|,to);
dis[now]=dis[now<<]+dis[now<<|];
}
int query(int now,int l,int r)
{
if(L[now]>=l&&R[now]<=r) return dis[now];
int res=;
if(l<=mid[now]) res+=query(now<<,l,r);
if(r>mid[now]) res+=query(now<<|,l,r);
return res;
}
};
struct TreeType tree1,tree2;
int n,m,q;
inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
}
int main()
{
in(n),in(m),in(q);
tree1.build(,,n);
tree2.build(,,m);
int op,x1,y1,x2,y2;
while(q--)
{
in(op),in(x1),in(y1);
if(op==) tree1.updata(,x1),tree2.updata(,y1);
else
{
in(x2),in(y2);
ll ans1=tree1.query(,x1,x2),ans2=tree2.query(,y1,y2);
printf("%lld\n",ans1*(y2-y1+)+ans2*(x2-x1+)-ans1*ans2*);
}
}
return ;
}
上一篇:GDALWarp设置GDALWarpOptions::dfWarpMemoryLimit过大时处理失败


下一篇:C#学习笔记(基础知识回顾)之值传递和引用传递