珂朵莉树RE求调
  • 板块P2391 白雪皑皑
  • 楼主_7Mr
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/11/9 17:34
  • 上次更新2023/11/9 19:59:22
查看原帖
珂朵莉树RE求调
602632
_7Mr楼主2023/11/9 17:34
#include<bits/stdc++.h>
#define int long long
#define double long double
#define INF INT_MAX
using namespace std;
const int maxn=1e7+5;
int n,m,p,q;
int a[maxn];
struct node {
	int l,r;
	mutable int v;
	node(int L,int R=0,int V=0) : l(L),r(R),v(V) {}
	bool operator < (const node &x) const {
		return l<x.l;
	}
};
set<node> ODT;
set<node>::iterator spilit(int pos) {
	set<node>::iterator it=ODT.lower_bound(node(pos));
	if(it!=ODT.end() && it->l==pos) return it;
	it--;
	if(it->r<pos) return ODT.end();
	int V=it->v,L=it->l,R=it->r;
	ODT.erase(it);
	ODT.insert(node(L,pos-1,V));
	return ODT.insert(node(pos,R,V)).first;
}
void bulldoze(int l,int r,int x) {
	set<node>::iterator itr=spilit(r+1),itl=spilit(l);
	ODT.erase(itl,itr);
	ODT.insert(node(l,r,x));
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>p>>q;
	ODT.insert(node(1,n+5));
	for(int i=1;i<=m;i++){
		bulldoze((i*p+q)%n+1,(i*q+p)%n+1,i);
//		cout<<(i*p+q)%n+1<<" "<<(i*q+p)%n+1<<" "<<i<<endl;
	}
	for(set<node>::iterator it=ODT.begin();it!=ODT.end();it++){
		for(int i=it->l;i<=it->r && i<=n;i++) cout<<it->v<<endl;
	}
	return 0;
}
2023/11/9 17:34
加载中...