Codeforces Round #757 (Div. 2) E. Divan and a Cottage

首先可以观察到一个性质：对与两个不同的起始温度t1和t2(t1 < t2),不管怎么变化温度，最终变化得到的温度T1和T2有T1 <= T2,容易想到维护一个关于起始温度的线段树，进行区间更新和单点查询。考虑到起始温度范围较大，故使用动态开点的方式进行处理：

#include<bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define debug(x) cout<<#x<<" is "<<x<<endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define DBG 0
#define lc(x) (x<<1)
#define rc(x) ((x << 1) | 1)
const int N = 2e5 + 5;
const int M = N * 240;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const ll LLINF = (1LL<<60);
using namespace std;
const double pi = acos(-1.0);
const int mod = 1e9 + 1;
ll fast_pow(ll a,ll b){ll ans = 1;while(b){if(b&1)ans = (ans * a)%mod;a = (a * a)%mod;b>>=1;}return (ans%mod);}
inline ll read(){ll X=0; bool flag=1; char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}if(flag) return X;return ~(X-1);}
inline void write(ll X){if(X<0) {X=~(X-1); putchar('-');}if(X>9) write(X/10);putchar(X%10+'0');}
typedef pair<int,int> pii;
typedef vector<int> vi;
inline void fastIO(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
inline void time_cost(clock_t start_time,clock_t end_time){cout << "The run time is: " <<(double)(end_time - start_time) / CLOCKS_PER_SEC << "s" << endl;}
inline void init(){	
	
}
int n,lst_ans = 0,x,q;
int lzy[M], fa[M][2],mn[M],mx[M],cnt;
int create(int L,int R){
	int t = ++cnt;
	mn[t] = L,mx[t] = R;
	return t;
}
void add(int x,int val){
	lzy[x] += val,mn[x] += val,mx[x] += val;
}
void up(int x){
	mn[x] = min(mn[fa[x][0]],mn[fa[x][1]]);
	mx[x] = max(mx[fa[x][0]],mx[fa[x][1]]);
}
void down(int x,int l,int r){
	if(l == r)return;
	int mid = (l + r) >> 1;
	if(!fa[x][0])fa[x][0] = create(l,mid);
	if(!fa[x][1])fa[x][1] = create(mid + 1,r);
	add(fa[x][0],lzy[x]),add(fa[x][1],lzy[x]),lzy[x] = 0;
}
int qL(int x,int l,int r,int v){
	if(l == r)return l;
	down(x,l,r);
	int mid = (l + r) >> 1;
	if(mn[fa[x][1]] <= v)
		return qL(fa[x][1],mid + 1,r,v);
	else
		return qL(fa[x][0],l,mid,v);
}
int qR(int x,int l,int r,int v){
	if(l == r)return l;
	down(x,l,r);
	int mid = (l + r) >> 1;
	if(mx[fa[x][0]] >= v)
		return qR(fa[x][0],l,mid,v);
	else
		return qR(fa[x][1],mid + 1,r,v); 
}
int qry(int x,int l,int r,int t){//和普通的查询还是有所不一样 
	if(!x)return t;
	if(l == r)return mn[x];
	int mid = (l + r ) >> 1;
	if(t <= mid)
		return qry(fa[x][0],l,mid,t) + lzy[x];
	else
		return qry(fa[x][1],mid + 1,r,t) + lzy[x];
}
void update(int x,int l,int r,int ql,int qr,int val){
	if(ql <= l && qr >= r){
		add(x,val);
		return;
	}
	down(x,l,r);
	int mid = (l + r) >> 1;
	if(ql <= mid)
		update(fa[x][0],l,mid,ql,qr,val);
	if(qr >= mid + 1)
		update(fa[x][1],mid + 1,r,ql,qr,val);
	up(x);
}
inline void solve(){
	init();
	cin >> n;
	create(0,1e9);
	for(int i = 1;i <= n;i++){
		cin >> x;
		if(mn[1] < x)update(1,0,1e9,0,qL(1,0,1e9,x - 1),1);
		if(mx[1] > x)update(1,0,1e9,qR(1,0,1e9,x + 1),1e9,-1);
		cin >> q;
		while(q--){
			cin >> x;
			int p = (lst_ans + x) % mod;
			lst_ans = qry(1,0,1e9,p);
			cout <<lst_ans <<endl;
		}
	}
} 
int main(){
	fastIO();
#if DBG
	freopen("input.txt","r",stdin); 
	freopen("output.txt","w",stdout);
#endif
//	int t;cin >> t;while(t--)
	solve();
	return 0;
}