欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Educational Codeforces Round 90 (Rated for Div. 2) - G. Pawns

程序员文章站 2022-05-11 18:17:52
...

题意:

一个 n×nn \times n 的棋盘上会有 mm 次变化,每次变化都会在某个空的位置上出现一个兵 或者 移去存在棋盘上的某个兵;
一个兵处于坐标 (x,y)(x,y) 可以移动到 (x,y+1)(x,y+1) , (x1,y+1)(x-1,y+1)(x+1,y+1)(x+1,y+1),前面是列,后面是行;
有一个特殊列 kk,每次变化,你都要计算把所有的兵移动到第 kk 列(不可以重叠),需要在棋盘上第 nn 行之后额外添加的最少行数;

分析:

根据题意,不论列坐标怎么移动,行坐标每次 +1+1 ,所以在一个兵最少移动次数 到达第 kk 列之后,如果当前坐标已经有兵了,那么就不断递增行坐标直到找到第一个空的位置(行不够了就加),则先把所有的兵移动到离它最近的第 kk 列的位置,并统计第 kk 列上所有位置的兵的个数,那么需要考虑的就是第 kk 列两个相邻有兵的位置之间的溢满情况以及对后续的影响;
如果只求一次那么不难想,第 kk 列从前到后遍历一遍维护溢满情况就可以了,但是这里每次变化都要求一遍,所以得需要一个维护方法:
我们知道,假设 (k,y)(k,y) 有兵且它对答案有影响,要么是前面溢满了得跳过它,否则它就是答案的起点;
所以我们把第 kk 列每个点的初始值设置为它的行坐标1-1 ,例如 (k,i)(k,i) 的初始值是 i1i-1 ,每次添加一个兵,若离它最近的第 kk 列坐标是 (k,y)(k,y) ,则把 [1,k][1,k] 区间全部加上 11 即可,明显可以用线段树维护。

代码:

#include<bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define st first
#define nd second
#define P pair<int,int>
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define frep(i,a,b) for(int i=a;i>=b;i--)
const int N = 2E5+10; 

int n,k,m;
int w[N<<3];
int add[N<<3];
int cnt[N<<1];

void build(int l,int r,int rt){
	if(l==r){
		w[rt]=l-1;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	w[rt]=max(w[ls],w[rs]);
}

void pushdown(int rt){
	if(add[rt]==0) return;
	w[ls]+=add[rt];
	w[rs]+=add[rt];
	add[ls]+=add[rt];
	add[rs]+=add[rt];
	add[rt]=0;
	return;
}

void upd(int l,int r,int rt,int L,int R,int x){
    if(L<=l&&r<=R){
    	  w[rt]+=x;
    	add[rt]+=x;
    	return;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(L<=mid) upd(l,mid,ls,L,R,x);
	if(R>mid) upd(mid+1,r,rs,L,R,x);
	w[rt]=max(w[ls],w[rs]);	
}

int qry(int l,int r,int rt,int L,int R)
{
	if(L<=l&&r<=R) return w[rt];
	pushdown(rt);
	int mid=(l+r)>>1;
	int ANS=0;
	if(L<=mid) ANS=max(ANS,qry(l,mid,ls,L,R));
	if(R>mid) ANS=max(ANS,qry(mid+1,r,rs,L,R));
	return ANS;
}

int main()
{
	//freopen("1.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>k>>m;
	build(1,n+n,1);
	set<P>s;
	set<int>D;
	
	while(m--)
	{
		int x,y; cin>>x>>y;
		int pos=y+(int)abs(x-k);
		P p=P(x,y);
		if(s.count(p))
		{
			--cnt[pos];
			if(cnt[pos]==0) D.erase(pos);
			upd(1,n+n,1,1,pos,-1);
			s.erase(p);
		}
		else
		{
			++cnt[pos];
			if(cnt[pos]==1) D.insert(pos);
			upd(1,n+n,1,1,pos,1);
			s.insert(p);
		}
		if(D.empty()) cout<<0;
	    else cout<<max(0,qry(1,n+n,1,1,*D.rbegin())-n);
	    cout<<endl;
	}	
} 
相关标签: 线段树 线段树