改了一下午,求调
查看原帖
改了一下午,求调
1052768
GTAH2333楼主2024/5/9 17:05
#include<iostream>
#include<algorithm> 
#include<utility>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5, maxn = 2e14, mod = 1e9 + 7,inv2 = 5e8 + 4;
struct node{
	ll l,r,len;
	ll num,rem,ans;
	int leaf;
}tree[N<<2];
struct option{
	ll x;
	int y, id;
};
int n;
option opt[N];
ll lsh[N],cnt;
void build(int L, int R, int i) {
	tree[i].l = lsh[L], tree[i].r = lsh[R + 1] - 1;
	tree[i].len = tree[i].r - tree[i].l + 1, tree[i].leaf = 1;
	if(L == R) {
		return;
	}
	int mid = (L + R) >> 1;
	if(L<=mid) build(L,mid,i<<1), tree[i].leaf = 0;
	if(mid<R) build(mid+1,R,i<<1|1), tree[i].leaf = 0;
	return;
}
pair<ll,ll> cha(ll nop,int i) {
	if(tree[i].num + nop > tree[i].len) {
		ll res = (tree[i].l + tree[i].r) % mod * tree[i].len % mod * inv2 % mod;
		return make_pair(res, tree[i].rem + tree[i].num + nop - tree[i].len);
	} else {
		ll res = (tree[i].l + tree[i].l + tree[i].num + nop - 1) % mod * (tree[i].num + nop) % mod * inv2 % mod;
		return make_pair(res, tree[i].rem);
	}
}
pair<ll,ll> change_up(ll nop,int i) {
	if(tree[i].leaf == 1) {
		return cha(nop,i);
	} 
	if(tree[i<<1].num + nop > tree[i<<1].len) {
		ll rea = (tree[i<<1].l + tree[i<<1].r) % mod * tree[i<<1].len % mod * inv2 % mod;
		pair<ll,ll> res = change_up(tree[i<<1].num + nop - tree[i<<1].len + tree[i<<1].rem,i<<1|1);
		return make_pair(rea+res.first,res.second);
	} else {
		pair<ll,ll> res = cha(tree[i<<1].rem,i<<1|1);
		pair<ll,ll> rea = change_up(nop,i<<1);
		return make_pair(res.first+rea.first,res.second);
	}
}
void updata(int i) {
	pair<ll,ll> re = change_up(tree[i<<1].rem,i<<1|1);
	tree[i].rem = re.second;
	tree[i].ans = re.first + tree[i<<1].ans;
	tree[i].num = tree[i<<1].num + tree[i<<1|1].num + tree[i<<1].rem + tree[i<<1|1].rem - tree[i].rem;
	return;
}
void change(ll x,int y,int i) {
	if(tree[i].leaf == 1) {
		if(tree[i].len >= y) {
			tree[i].num = y;
			tree[i].rem = 0;
		} else {
			tree[i].num = tree[i].len;
			tree[i].rem = y - tree[i].len;
		}
		tree[i].ans = (tree[i].l + tree[i].l + tree[i].num - 1) % mod * tree[i].num % mod * inv2 % mod;
		return;
	}
	if(x<=tree[i<<1].r) change(x,y,i<<1);
	else change(x,y,i<<1|1);
	updata(i);
}
int main() {
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;++i) {
		cin>>opt[i].x>>opt[i].y;
		if(opt[i].x != 1 ) lsh[++cnt] = opt[i].x;
	}
	sort(lsh+1,lsh+cnt+1);
	int m = unique(lsh+1,lsh+cnt+1) - lsh - 1;
	lsh[0] = 1, lsh[m+1] = maxn+1;
	build(0,m,1);
	for(int i=1;i<=n;++i) {
		change(opt[i].x,opt[i].y,1);
		cout<<(tree[1].ans + mod )%mod<<endl;
	}
	return 0;
}

只过了前两个

2024/5/9 17:05
加载中...