萌新刚学OI,整体二分只过hack数据 求调!
查看原帖
萌新刚学OI,整体二分只过hack数据 求调!
286448
Eason2009楼主2022/8/25 08:33
#include<bits/stdc++.h>
#define maxn 400005
using namespace std;
int n,m,l1[maxn],r1[maxn],kth[maxn],tot,ans[maxn],tree[maxn],ask[maxn],mx=2e5;
struct node
{
	int id,l,r,num,k;
}q[maxn],q1[maxn],q2[maxn];
void update(int x,int k)
{
	while(x<=mx)
	{
		tree[x]+=k;
		x+=x&(-x);
	}
	return;
}
int query(int x)
{
	int sum=0;
	while(x)
	{
		sum+=tree[x];
		x-=x&(-x);
	}
	return sum;
}
void solve(int ql,int qr,int l,int r)
{
	if(ql>qr||l>r) return;
	if(ql==qr)
	{
		for(int i=l;i<=r;i++)
		{
			if(!q[i].id&&q[i].l<=ask[ql]&&q[i].r>=ask[ql]) ans[ql]++;
		}
		return;
	}
	int mid=ql+qr>>1,tot1=0,tot2=0;
	for(int i=l;i<=r;i++)
	{
		if(q[i].id)
		{
			if(q[i].id<=mid) update(q[i].num,1),q1[++tot1]=q[i];
			else q2[++tot2]=q[i];
		}
		else
		{
			int res=query(q[i].r)-query(q[i].l-1);
			if(res>=q[i].k) q1[++tot1]=q[i];
			else q[i].k-=res,q2[++tot2]=q[i];
		}
	}
	for(int i=1;i<=tot1;i++)
	{
		if(q1[i].id) update(q1[i].num,-1);
	}
	for(int i=1;i<=tot1;i++)
	{
		q[l+i-1]=q1[i];
	}
	for(int i=1;i<=tot2;i++)
	{
		q[l+tot1+i-1]=q2[i];
	}
	solve(ql,mid,l,l+tot1-1);
	solve(mid+1,qr,l+tot1,l+tot1+tot2-1);
	return;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>l1[i]>>r1[i]>>kth[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>ask[i];
		q[++tot]=(node){i,0,0,ask[i],0};
	}
	for(int i=1;i<=n;i++)
	{
		q[++tot]=(node){0,l1[i],r1[i],0,kth[i]};
	}
	solve(1,m,1,tot);
	for(int i=1;i<=m;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}

而且所有错误的点都是在200000行(也就是最后一行)的答案错了,不知道为什么。

2022/8/25 08:33
加载中...