关于最后统计答案方式
查看原帖
关于最后统计答案方式
251324
stntn楼主2022/5/6 17:59

rt我尝试了两种输出方式,为什么第一种是错的?

第一种,将答案存在 NODE\text{NODE} 里,最后排序再输出

第二种,将答案存在 ans\text{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;
}
2022/5/6 17:59
加载中...