50求调---悬棺
查看原帖
50求调---悬棺
1061339
Tracy_Loght楼主2025/1/2 17:06










#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[5000001];
ll k[5000001],f[5000001],v=1;
struct {
	ll l,r,x,lb;
} o[5000001];
char buf[1<<20],*p1,*p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin), p1 == p2) ? 0 : *p1++)
template<typename T>inline void readT(T &x){
    bool f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=(f?x:-x);return;
}
inline void read128(__int128 &x){
    bool f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=(f?x:-x);return;
}
void bulid(ll l,ll r,ll c) {
	if(l>r)return ;
	o[c].l=l;
	o[c].r=r;
	if(l==r) o[c].x=a[l];
	else {
		ll mid=l+(r-l)/2;
		bulid(l,mid,c*2);
		bulid(mid+1,r,c*2+1);
		o[c].x=o[c*2].x+o[c*2+1].x;
	}
}
void uptree() {
	for(ll i=1; i<=n; i++) readT(k[i]);
	for(ll i=1; i<=n; i++) a[i]=1;
	for(ll i=1;i<=n;i++) f[i]=1;
	bulid(1,n,1);
	return ;
}
void write(ll c) {
	if(o[c].lb!=0) {
		o[c*2].x+=o[c].lb*(o[c*2].r-o[c*2].l+1);
		o[c*2+1].x+=o[c].lb*(o[c*2+1].r-o[c*2+1].l+1);
		o[c*2].lb+=o[c].lb;
		o[c*2+1].lb+=o[c].lb;
		o[c].lb=0;
	}
}
void dcc(ll l,ll r,ll cl,ll cr,ll c,ll lz) {
	if(l>r||cl>cr) return ;
	if(cr<l||cl>r) return ;
	if(cl<=l&&cr>=r) {
		o[c].lb+=lz;
		o[c].x+=(r-l+1)*lz;
	} else {
		write(c);
		ll mid=l+(r-l)/2;
		dcc(l,mid,cl,cr,c*2,lz);
		dcc(mid+1,r,cl,cr,c*2+1,lz);
		o[c].x=o[c*2].x+o[c*2+1].x;
	}
}
ll cpz(ll l,ll r,ll cl,ll cr,ll f,ll lz,ll c) {
	if(l>r||cl>cr) return 0;
	if(cr<l||cl>r) return 0;
	if(cl<=l&&cr>=r) return o[c].x;
	write(c);
	ll mid=l+(r-l)/2;
	return cpz(l,mid,cl,cr,f,lz,c*2)
	       +cpz(mid+1,r,cl,cr,f,lz,c*2+1);
}
void orb(ll l,ll r,ll x){
//	cout<<l<<" "<<r<<" "<<x<<"\n";
	if(r<l) return;
	if(l<=0||r>n) return;
	ll mid=l+(r-l)/2,kc=0;
	if(kc==x) return ;
	kc=cpz(1,n,v,mid,0,0,1);
	if(kc==x) {v=mid+1;return;}
	else if(kc>x) orb(l,mid,x);
	else if(kc<x) orb(mid+1,r,x);
}
int main() {
	ios::sync_with_stdio(0);
	std::cin.tie();
	std::cout.tie();
	readT(n); uptree();
	for(int i=1;i<=n;i++){
		k[i]=k[i]%cpz(1,n,1,n,0,0,1);
		int asd=0,jk=cpz(1,n,v,n,0,0,1);
		if(jk<k[i]){k[i]-=jk;v=1;}
		orb(v,n,k[i]);
		if(v>n) v=v-n;
		if(v>n) v=v-n;
//		cout<<v<<" ";v++;
		for(int j=v;j<=n;j++){
			if(f[j]==1){
				v=j+1;cout<<j<<"\n";
				dcc(1,n,j,j,1,-1);
				asd=1; f[j]=0; break;
			}
		}
		if(asd==0){
			for(int j=1;j<=v;j++){
				if(f[j]==1){
					v=j+1;cout<<j<<"\n";
					dcc(1,n,j,j,1,-1);
					asd=1; f[j]=0; break; 
				}
			}
		}
		if(v>n) v=v-n;
		if(v>n) v=v-n;
//		for(int j=1;j<=2*n;j++){
//			cout<<o[j].l<<" "<<o[j].r<<" "<<o[j].x<<"\n";
//		}
	}
	return 0;
}
/*
	cin>>a;dcc(1,n,a,a,1,-1);//删除一张牌
	cin>>l>>r;cpz(1,n,l,r,0,0,1);//求一段有多少可用牌
*/
2025/1/2 17:06
加载中...