题目
代码
首先容易想到对于所有的初始温度，其答案一定构成一段一段的区间，然后因为题目强制在线，可以想到每一天后就维护一下当前的答案集合。
容易发现，其实本质就是对于答案大于某一个数的所有数进行区间减，对于答案小于某个数的所有数区间加。（因为刚刚说了构成连续区间）
那么现在的问题就在于如何求出这两段区间。
显然可以线段树上二分来做，需要记录一下区间答案最大值和区间答案最小值。
然后这题需要动态开点，并且在开点的时候才去分配最大值和最小值，而动态开点的过程就在 \(pushdown\) 里面即可，注意边界的判断。
时间复杂度 \(O(n\log n)\) 。
代码
#include<bits/stdc++.h>
using namespace std;
//#ifdef ONLINE_JUDGE
// #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
// char buf[1<<21],*p1=buf,*p2=buf;
//#endif
template<typename T>
inline void read(T &x){
x=0;bool f=false;char ch=getchar();
while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template<typename T>
inline void write(T x){
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define PII pair<int,int>
#define rep(i,x,y) for(register int i=(x);i<=(y);i++)
#define dep(i,y,x) for(register int i=(y);i>=(x);i--)
#define repg(i,x) for(int i=head[x];i;i=nex[i])
#define filp(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define infilp(s) freopen(s".in","r",stdin)
#define outfilp(s) freopen(s".out","w",stdout)
const int MOD=1e9+7;
inline int inc(int x,int y){x+=y;return x>=MOD?x-MOD:x;}
inline int dec(int x,int y){x-=y;return x<0?x+MOD:x;}
inline void incc(int &x,int y){x+=y;if(x>=MOD) x-=MOD;}
inline void decc(int &x,int y){x-=y;if(x<0) x+=MOD;}
inline void chkmin(int &x,int y){if(y<x) x=y;}
inline void chkmax(int &x,int y){if(y>x) x=y;}
const int N=2e5+5,M=2e5+5,INF=1e9+7;
int n,las;
int ls[N<<6],rs[N<<6],Maxn[N<<6],Minn[N<<6],tag[N<<6],cur,root;
inline void Newnode(int &x,int l,int r){
x=++cur;
Minn[x]=l,Maxn[x]=r;
return ;
}
inline void Pushup(int x){
Maxn[x]=Maxn[rs[x]];Minn[x]=Minn[ls[x]];
return ;
}
inline void PushDown(int x,int l,int r){
int mid=l+r>>1;
if(!ls[x]) Newnode(ls[x],l,mid);
if(!rs[x]) Newnode(rs[x],mid+1,r);
const int lc=ls[x],rc=rs[x];
Maxn[lc]+=tag[x],Maxn[rc]+=tag[x];
Minn[lc]+=tag[x],Minn[rc]+=tag[x];
tag[lc]+=tag[x],tag[rc]+=tag[x];
tag[x]=0;
Pushup(x);
return ;
}
void Modify(int &x,int l,int r,int ql,int qr,int v){
if(!x) Newnode(x,l,r);
if(ql<=l&&r<=qr) return Maxn[x]+=v,Minn[x]+=v,tag[x]+=v,void();
int mid=l+r>>1;PushDown(x,l,r);
if(ql<=mid) Modify(ls[x],l,mid,ql,qr,v);
if(qr>mid) Modify(rs[x],mid+1,r,ql,qr,v);
Pushup(x);
return ;
}
int Query(int x,int l,int r,int pos){//查询单点真实温度
if(pos==-1) return -1;
if(l==r) return Maxn[x];
int mid=l+r>>1;PushDown(x,l,r);
if(pos<=mid) return Query(ls[x],l,mid,pos);
return Query(rs[x],mid+1,r,pos);
}
int Ql(int x,int l,int r,int pos){//查询温度小于pos的最后一个位置
if(l==r) return l;
// cout<<tag[x]<<endl;
int mid=l+r>>1;PushDown(x,l,r);
// cout<<"Ql:"<<l<<' '<<r<<' '<<Minn[ls[x]]<<' '<<Minn[rs[x]]<<' '<<mid+1<<' '<<tag[rs[x]]<<' '<<pos<<endl;
if(Minn[rs[x]]<pos) return Ql(rs[x],mid+1,r,pos);
return Ql(ls[x],l,mid,pos);
}
int Qr(int x,int l,int r,int pos){
if(l==r) return l;
int mid=l+r>>1;PushDown(x,l,r);
if(Maxn[ls[x]]>pos) return Qr(ls[x],l,mid,pos);
return Qr(rs[x],mid+1,r,pos);
}
signed main(){
// double ST=clock();
// ios::sync_with_stdio(false);
//#ifndef ONLINE_JUDGE
// filp("my");
//#endif
read(n);
Newnode(root,0,1e9);
rep(i,1,n){
int tmp,k,x,p1=-1,p2=-1;
read(tmp),read(k);
if(Maxn[root]>tmp) p1=Qr(root,0,1e9,tmp);
if(Minn[root]<tmp) p2=Ql(root,0,1e9,tmp);
// cout<<p1<<' '<<p2<<"!!\n";
// cout<<Query(root,0,1e9,p1)<<' '<<Query(root,0,1e9,p2)<<"??\n";
if(Maxn[root]>tmp) Modify(root,0,1e9,p1,1e9,-1);
if(Minn[root]<tmp) Modify(root,0,1e9,0,p2,1);
rep(j,1,k){
read(x);
x=(x+las)%((int)1e9+1);
// cout<<x<<"?\n";
las=Query(root,0,1e9,x);
write(las),pc('\n');
}
}
// cerr<<"\nTime:"<<(clock()-ST)/CLOCKS_PER_SEC<<"s\n";
return 0;
}
/*
*/