求助一种新的做法
  • 板块P2184 贪婪大陆
  • 楼主Xeqwq
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/4/27 08:13
  • 上次更新2023/10/28 02:49:55
查看原帖
求助一种新的做法
229373
Xeqwq楼主2022/4/27 08:13

rt,题解中没有看到,不知道是否可行:
在查询 [l,r][l,r] 的时候,用总的地雷种数 减去 [1,l1][1,l-1] 的地雷总数再减去 [r+1,n][r+1,n]的地雷总数,即
ans=cnt-query(1,l-1)-query(r+1,n)
(与代码格式略有出入)
实测有些问题(样例没过,输出两个1),可能是自己代码的问题(那就求调吧)
上代码:

#include <iostream>
using namespace std;
inline int lc(int p){return p<<1;}
inline int rc(int p){return p<<1|1;}
const int Maxn=1e5+2e4;
int n,m;
int sum[2][Maxn*4];
void pushup(int p,int c)
{
	sum[c][p]=sum[c][lc(p)]+sum[c][rc(p)];
}
void modify(int p,int l,int r,int c,int x)
{
	if(l==r)
	{
		sum[c][x]++;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) modify(lc(p),l,mid,c,x);
	else modify(rc(p),mid+1,r,c,x);
	pushup(p,c);
}
int query(int p,int l,int r,int c,int ql,int qr)
{
	if(ql<=l&&r<=qr) return sum[c][p];
	int mid=(l+r)>>1,res=0;
	if(ql<=mid) res+=query(lc(p),l,mid,c,ql,qr);
	if(mid<qr) res+=query(rc(p),mid+1,r,c,ql,qr);
	return res;
}
int main()
{
	int cnt=0;
	scanf("%d%d",&n,&m);
	int op,x,y;
	while(m--)
	{
		scanf("%d%d%d",&op,&x,&y);
		if(op==1)
		{
			++cnt;
			modify(1,1,n,0,x);
			modify(1,1,n,1,y+1);
		}
		else
		{
			int ans=cnt;
			if(y<n) ans-=query(1,1,n,0,y+1,n);
			if(x>1) ans-=query(1,1,n,1,1,x-1);
			printf("%d\n",ans);
		}
	}
}
2022/4/27 08:13
加载中...