結果

問題 No.1862 Copy and Paste
コンテスト
ユーザー vjudge1
提出日時 2024-11-13 11:04:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,953 bytes
コンパイル時間 2,546 ms
コンパイル使用メモリ 212,144 KB
最終ジャッジ日時 2025-02-25 04:03:04
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other WA * 5 RE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,q,a[N],b[N];
priority_queue<int> que[N]; 
set<int> s[N];
map<int,int> ma[N];
struct TREE {
	int l,r,val;
}tr[N<<2];
void pushup(int p) {
	tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
}
void build(int p,int pl,int pr) {
	tr[p].l=pl; tr[p].r=pr;
	if(pl==pr) {
		tr[p].val=b[pl];
		return;
	}
	int mid=(pl+pr)>>1;
	build(p<<1,pl,mid);
	build(p<<1|1,mid+1,pr);
	pushup(p);
}
void init() {
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		s[a[i]].insert(i);
	}
	for(int i=0;i<=n+1;i++) {
		s[i].insert(0);
		s[i].insert(n+1);
	}
	for(int i=0;i<=n+1;i++) {
		int las=0;
		for(auto j:s[i]) {
			int dis=j-las-1;
			b[i]=max(b[i],dis);
			que[i].push(dis);
			las=j;
		}
	}
	build(1,0,n+1);
}
void update(int p,int L,int d) {
	if(tr[p].l==L&&L==tr[p].r) {
		tr[p].val=d;
		return;
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	if(L<=mid) update(p<<1,L,d);
	else update(p<<1|1,L,d);
	pushup(p);
}
int query(int p,int x) {
//	cout<<p<<" "<<tr[p].l<<" "<<tr[p].r<<" "<<tr[p].val<<endl;
	if(tr[p].l==tr[p].r) return tr[p].l;
	int mid=(tr[p].l+tr[p].r)>>1;
	if(tr[p<<1].val>=x) return query(p<<1,x);
	else return query(p<<1|1,x);
}
void upd(int x,int y,int z) {
	auto op1=s[x].lower_bound(y),opp=op1; //??  
	int l=*(--opp),r;
	opp=op1; r=*(++opp);
	ma[x][y-l-1]++; ma[x][r-y-1]++;
	
	s[x].erase(y);
	s[x].insert(z);
	
	op1=s[x].lower_bound(z),opp=op1; //?? 
	l=*(--opp);
	opp=op1; r=*(++opp);
	que[x].push(z-l-1); que[x].push(r-z-1);
	
	while(ma[x][que[x].top()]) {
		ma[x][que[x].top()]--;
		que[x].pop();
	}
	update(1,x,que[x].top());
}
signed main() {
	ios::sync_with_stdio(false);
//	freopen("star.in","r",stdin);
//	freopen("star.out","w",stdout);
	init();
	while(q--) {
		int op,x;
		cin>>op>>x;
		if(op==1) {
			upd(a[x],x,x+1);
			upd(a[x+1],x+1,x);
			swap(a[x],a[x+1]);
//			cout<<"MAN "<<que[a[x+1]].top()<<" "<<que[a[x]].top()<<endl;
		} else {
			cout<<query(1,x)<<endl;
		}
	}
	return 0;
}
0