rt我尝试了两种输出方式,为什么第一种是错的?
第一种,将答案存在 NODE 里,最后排序再输出
第二种,将答案存在 ans 数组里,最后输出
#include<bits/stdc++.h>
#define N 200010
#define M 2000020
#define int long long
#define ULL unsigned long long
#define DB double
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define tep(i,u) for(int i=head[u];~i;i=e[i].nxt)
#define INF 0x3f3f3f3f
using namespace std;
template <typename T> inline void read(T &a)
{
a=0;T w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+(ch^48);ch=getchar();}
a*=w;
}
template <typename T,typename ...Args> inline
void read(T &x,Args &...args){read(x);read(args...);}
int w,n,opt,cc,ans[N];
struct NODE
{
int a,b,c,id,ans;bool typ;
NODE(){}
NODE(int _a,int _b,int _c,bool _typ,int _id): a(_a),b(_b),c(_c),typ(_typ),id(_id){}
}a[N];
inline bool cmp1(NODE x,NODE y){return (x.a^y.a) ? x.a<y.a : ((x.b^y.b) ? x.b<y.b : x.id>y.id);}
inline bool cmp2(NODE x,NODE y){return x.c<y.c;}
class BIT
{
public:
int sum[M];
inline int lowbit(int x){return x&-x;}
inline void update(int x,int val){for(;x<=w;x+=lowbit(x)) sum[x]+=val;}
inline int query(int x){int res=0;for(;x;x-=lowbit(x)) res+=sum[x];return res;}
}t;
inline void cdq(int l,int r)
{
if(l==r) return;int mid=l+r>>1;
cdq(l,mid);cdq(mid+1,r);
sort(a+l,a+mid+1,cmp1);
sort(a+mid+1,a+r+1,cmp1);
int j=l;
rep(i,mid+1,r)
{
while(a[i].a>=a[j].a&&j<=mid)
{
if(a[j].typ) t.update(a[j].b,a[j].id);
j++;
}
// if(!a[i].typ) a[i].ans+=t.query(a[i].b);//第一种 全WA
if(!a[i].typ) ans[a[i].id]+=t.query(a[i].b);//第二种 AC
}
rep(i,l,j-1) if(a[i].typ) t.update(a[i].b,-a[i].id);
}
signed main()
{
read(w);read(w);w+=10;
read(opt);
while(opt!=3)
{
if(opt==1)
{
int x,y,val;read(x,y,val);x++;y++;
++n;a[n]={x,y,n,1,val};
}
else
{
int x,y,_x,_y;read(_x,_y,x,y);x++;y++;
++n;a[n]={x,y,n,0,++cc};
++n;a[n]={_x,_y,n,0,++cc};
++n;a[n]={_x,y,n,0,++cc};
++n;a[n]={x,_y,n,0,++cc};
}
read(opt);
}
cdq(1,n);
//第一种 全WA
// sort(a+1,a+1+n,cmp2);
// rep(i,1,n)
// {
// if(a[i].typ) continue;
// printf("%lld\n",a[i].ans+a[i+1].ans-a[i+2].ans-a[i+3].ans);
// i+=3;
// }
//第二种 AC
int res=0;cc>>=2;
rep(i,1,cc)
{
int j=(i-1)*4+1;
printf("%lld\n",ans[j]+ans[j+1]-ans[j+2]-ans[j+3]);
}
return 0;
}