NC20814. 红魔法师
描述
输入描述
第一行n。
接下来每行第一个数1,2分别表示加入,删除。
后两个数x,y为点的坐标。
输出描述
n行每行一个正整数。
示例1
输入:
6 1 1 1 1 2 2 1 3 3 2 1 1 1 1 2 1 1 1
输出:
0 0 1 0 0 2
C++14(g++5.4) 解法, 执行用时: 5914ms, 内存消耗: 12584K, 提交时间: 2018-12-26 11:18:34
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define add(x,y) (((1LL*(x)+(y))%mod+mod)%mod)
#define mul(x,y) (((1LL*(x)*(y))%mod+mod)%mod)
#define filein(x) freopen(#x".in","r",stdin)
#define fileout(x) freopen(#x".out","w",stdout)
#define For(a,v) for(auto a:v)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int mod=1e9+7;
const int maxn=6e4+93;
const int inf=0x3f3f3f3f;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int S=270;
int n,m,cur,ans,root;
int x[maxn],y[maxn];
pii tmp[maxn];
struct P
{
int mn[2],mx[2],d[2],lch,rch;
int & operator[] (int x) { return d[x]; }
friend bool operator < (P x,P y)
{
return x[cur]<y[cur];
}
friend int dis(P x,P y)
{
return abs(x[0]-y[0])+abs(x[1]-y[1]);
}
bool allin(int x1,int x2,int y1,int y2)
{
return mn[0]>=x1&&mx[0]<=x2&&mn[1]>=y1&&mx[1]<=y2;
}
bool allout(int x1,int x2,int y1,int y2)
{
return mx[0]<x1||mn[0]>x2||mx[1]<y1||mn[1]>y2;
}
bool in(int x1,int x2,int y1,int y2)
{
return x1<=d[0]&&d[0]<=x2&&y1<=d[1]&&d[1]<=y2;
}
}p[maxn];
int op[maxn];
struct kdtree
{
P t[maxn],T;
LL ans[maxn];
LL suma[maxn];
LL sumb[maxn];
LL sumc[maxn];
LL num[maxn];
LL a[maxn];
LL b[maxn];
LL c[maxn];
LL isopen[maxn];
LL taga[maxn];
LL tagb[maxn];
LL tagc[maxn];
void pushup(int k)
{
int l=t[k].lch,r=t[k].rch;
suma[k]=suma[l]+suma[r]+a[k]*isopen[k];
sumb[k]=sumb[l]+sumb[r]+b[k]*isopen[k];
sumc[k]=sumc[l]+sumc[r]+c[k]*isopen[k];
num[k]=num[l]+num[r]+isopen[k];
ans[k]=ans[l]+ans[r]+
(a[k]*(a[k]-1)-2*b[k]*c[k])*isopen[k];
}
void makeflaga(int k,LL x)
{
taga[k]+=x;
ans[k]+=2*x*suma[k]+x*(x-1)*num[k];
suma[k]+=x*num[k];
a[k]+=x;
}
void makeflagb(int k,LL x)
{
tagb[k]+=x;
ans[k]-=2*x*sumc[k];
sumb[k]+=x*num[k];
b[k]+=x;
}
void makeflagc(int k,LL x)
{
tagc[k]+=x;
ans[k]-=2*x*sumb[k];
sumc[k]+=x*num[k];
c[k]+=x;
}
void pushdown(int k)
{
if(t[k].lch==0&&t[k].rch==0)
return ;
if(taga[k])
{
if(t[k].lch)makeflaga(t[k].lch,taga[k]);
if(t[k].rch)makeflaga(t[k].rch,taga[k]);
taga[k]=0;
}
if(tagb[k])
{
if(t[k].lch)makeflagb(t[k].lch,tagb[k]);
if(t[k].rch)makeflagb(t[k].rch,tagb[k]);
tagb[k]=0;
}
if(tagc[k])
{
if(t[k].lch)makeflagc(t[k].lch,tagc[k]);
if(t[k].rch)makeflagc(t[k].rch,tagc[k]);
tagc[k]=0;
}
}
void update(int k)
{
int l=t[k].lch,r=t[k].rch;
for(int i=0;i<2;i++)
{
t[k].mn[i]=t[k].mx[i]=t[k][i];
if(l) t[k].mn[i]=min(t[l].mn[i],t[k].mn[i]);
if(r) t[k].mn[i]=min(t[r].mn[i],t[k].mn[i]);
if(l) t[k].mx[i]=max(t[l].mx[i],t[k].mx[i]);
if(r) t[k].mx[i]=max(t[r].mx[i],t[k].mx[i]);
}
}
int build(int l,int r,int now)
{
cur=now;
int mid=(l+r)>>1;
nth_element(p+l,p+mid,p+r+1);
t[mid]=p[mid];
for(int i=0;i<2;i++) t[mid].mx[i]=t[mid].mn[i]=t[mid][i];
if(l<mid) t[mid].lch=build(l,mid-1,now^1);
if(r>mid) t[mid].rch=build(mid+1,r,now^1);
update(mid);
return mid;
}
void modify(int k,int v)
{
if(t[k].allout(T[0],T[0],T[1],T[1])) return ;
pushdown(k);
if(t[k][0]==T[0]&&t[k][1]==T[1])
{
isopen[k]+=v;
pushup(k);
return ;
}
int l=t[k].lch;
int r=t[k].rch;
modify(l,v);
modify(r,v);
pushup(k);
}
void modifya(int k,int x1,int x2,int y1,int y2,int v)
{
if(t[k].allout(x1,x2,y1,y2)) return;
//printf("ce %d\n",k);
if(t[k].allin(x1,x2,y1,y2))
{
makeflaga(k,v);
return;
}
pushdown(k);
if(t[k].in(x1,x2,y1,y2)) a[k]+=v;
modifya(t[k].lch,x1,x2,y1,y2,v);
modifya(t[k].rch,x1,x2,y1,y2,v);
pushup(k);
}
void modifyb(int k,int x1,int x2,int y1,int y2,int v)
{
if(t[k].allout(x1,x2,y1,y2)) return;
if(t[k].allin(x1,x2,y1,y2))
{
makeflagb(k,v);
return;
}
pushdown(k);
if(t[k].in(x1,x2,y1,y2)) b[k]+=v;
modifyb(t[k].lch,x1,x2,y1,y2,v);
modifyb(t[k].rch,x1,x2,y1,y2,v);
pushup(k);
}
void modifyc(int k,int x1,int x2,int y1,int y2,int v)
{
if(t[k].allout(x1,x2,y1,y2)) return;
if(t[k].allin(x1,x2,y1,y2))
{
makeflagc(k,v);
return;
}
pushdown(k);
if(t[k].in(x1,x2,y1,y2)) c[k]+=v;
modifyc(t[k].lch,x1,x2,y1,y2,v);
modifyc(t[k].rch,x1,x2,y1,y2,v);
pushup(k);
}
void query(int x,int y,int v)
{
T[0]=x,T[1]=y;
//printf("%d %d\n",x,y);
modify(root,v);
modifya(root,x+1,inf,y+1,inf,v);
modifyb(root,x+1,inf,y,y,v);
modifyc(root,-inf,x-1,-inf,y-1,v);
}
}kdtree;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&op[i],&x[i],&y[i]);
if(op[i]==2)op[i]=-1;
tmp[i]=make_pair(x[i],y[i]);
}
sort(tmp+1,tmp+n+1);
int np=unique(tmp+1,tmp+n+1)-tmp-1;
for(int i=1;i<=np;i++)
{
p[i][0]=tmp[i].first,p[i][1]=tmp[i].second;
}
root = kdtree.build(1,np,0);
for(int i=1;i<=n;i++)
{
kdtree.query(x[i],y[i],op[i]);
printf("%lld\n",kdtree.ans[root]/2);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 6433ms, 内存消耗: 12128K, 提交时间: 2018-10-29 13:10:45
//#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct TR{
int l, r, d, u, ty;
int val;
ll sum[3], laz[3];
}tr[404000];
#define pii pair<int,int>
#define fi first
#define se second
int n, m;
pii p[101000];
struct OPT{
int ty; pii p;
}a[101000];
void Umn(int &x,int y){ x=min(x,y); }
void Umx(int &x,int y){ x=max(x,y); }
bool xxx(const pii &a,const pii &b){ return a.fi<b.fi; }
bool yyy(const pii &a,const pii &b){ return a.se<b.se; }
void build(int x,int l,int r,int ty){
TR &o=tr[x]; o.ty=ty;
o.l=1e9; o.r=0; o.d=1e9; o.u=0;
for (int i=l;i<=r;++i){
Umn(o.l,p[i].fi); Umx(o.r,p[i].fi);
Umn(o.d,p[i].se); Umx(o.u,p[i].se);
}
if (o.l==o.r&&o.d==o.u) return;
int mid=l+r>>1;
if (ty==1){
nth_element(p+l,p+mid,p+r+1,xxx);
}else if (ty==2){
nth_element(p+l,p+mid,p+r+1,yyy);
}
build(x<<1,l,mid,ty^3);
build(x<<1|1,mid+1,r,ty^3);
}
void PT(int x,ll v,int who){
tr[x].sum[who]+=tr[x].val*v;
tr[x].laz[who]+=v;
}
void D(int x,int who){
if (tr[x].laz[who]){
PT(x<<1,tr[x].laz[who],who);
PT(x<<1|1,tr[x].laz[who],who);
tr[x].laz[who]=0;
}
}
void D(int x){
D(x,0); D(x,1); D(x,2);
}
void U(int x,int who){
if (~who) tr[x].sum[who]=tr[x<<1].sum[who]+tr[x<<1|1].sum[who];
else tr[x].val=tr[x<<1].val+tr[x<<1|1].val;
}
void U(int x){
U(x,-1); U(x,0); U(x,1); U(x,2);
}
void cg(int x,int l,int r,int d,int u,int v,int who){
TR &o=tr[x];
Umx(l,o.l); Umn(r,o.r); if (l>r) return;
Umx(d,o.d); Umn(u,o.u); if (d>u) return;
if (o.l==l&&o.r==r&&o.d==d&&o.u==u){
PT(x,v,who); return;
}
D(x,who);
cg(x<<1,l,r,d,u,v,who);
cg(x<<1|1,l,r,d,u,v,who);
U(x,who);
}
ll calval(int x,int l,int r,int d,int u){
TR &o=tr[x];
Umx(l,o.l); Umn(r,o.r); if (l>r) return 0;
Umx(d,o.d); Umn(u,o.u); if (d>u) return 0;
if (o.l==l&&o.r==r&&o.d==d&&o.u==u){
return o.val;
}
return
calval(x<<1,l,r,d,u)+
calval(x<<1|1,l,r,d,u);
}
ll calsum(int x,int l,int r,int d,int u,int who){
TR &o=tr[x];
Umx(l,o.l); Umn(r,o.r); if (l>r) return 0;
Umx(d,o.d); Umn(u,o.u); if (d>u) return 0;
if (o.l==l&&o.r==r&&o.d==d&&o.u==u){
return o.sum[who];
}
D(x,who);
return
calsum(x<<1,l,r,d,u,who)+
calsum(x<<1|1,l,r,d,u,who);
}
void reset(int x,int lr,int du,ll v,ll s0,ll s1,ll s2){
TR &o=tr[x];
if (!(o.l<=lr&&lr<=o.r)) return;
if (!(o.d<=du&&du<=o.u)) return;
if (o.l==o.r&&o.d==o.u){
o.val=v; o.sum[0]=s0; o.sum[1]=s1; o.sum[2]=s2;
return;
}
D(x);
reset(x<<1,lr,du,v,s0,s1,s2);
reset(x<<1|1,lr,du,v,s0,s1,s2);
U(x);
}
ll ans;
int main(){
cin>>n;
for (int i=1;i<=n;++i){
scanf("%d%d%d",&a[i].ty,&a[i].p.fi,&a[i].p.se);
p[++m]=a[i].p;
}
sort(p+1,p+m+1);
m=unique(p+1,p+m+1)-p-1;
build(1,1,m,1);
for (int i=1;i<=n;++i){
OPT o=a[i]; int x=o.p.fi, y=o.p.se;
if (o.ty==1){
int c=calval(1, 1,x-1, y,y);
int low=calval(1, 1,x-1, 1, y-1);
int hig=calval(1, x+1,n, y+1,n);
ans+=(ll)low*(low-1)/2;
ans-=calsum(1, 1, x-1, 1, y-1, 2);
ans+=calsum(1, x+1,n, y+1,n, 0);
ans-=(ll)c* calval(1, x+1,n, y+1,n);
ans-=calsum(1, x+1,n, y,y, 1);
cg(1, x+1,n, y+1,n, 1, 0);
cg(1, 1,x-1, 1,y-1, 1, 1);
cg(1, x+1,n, y,y, 1, 2);
reset(1, x,y, 1,low,hig,c);
}else{
reset(1, x,y, 0,0,0,0);
int c=calval(1, 1,x-1, y,y);
int low=calval(1, 1,x-1, 1, y-1);
//int hig=calval(1, x+1,n, y+1,n);
cg(1, x+1,n, y+1,n, -1, 0);
cg(1, 1,x-1, 1,y-1, -1, 1);
cg(1, x+1,n, y,y, -1, 2);
ans-=calsum(1, x+1,n, y+1,n, 0);
ans+=(ll)c* calval(1, x+1,n, y+1,n);
ans+=calsum(1, x+1,n, y,y, 1);
ans-=(ll)low*(low-1)/2;
ans+=calsum(1, 1, x-1, 1, y-1, 2);
}
printf("%lld\n",ans);
}
}