题意:
第一行三个数n,m,q ,人数,(进行淘汰和替换的)操作次数,询问数(询问前还有一次操作更改操作,而且每次更改会影响到后面)。
第二行n 个数,每个数字代表这个人的能力值
接下来m行,每行一开始有个num,表示这次要淘汰多少人,
然后num个数字,表示这次操作补充进来的人的能力值(保证每年都有n 个人)。
接下来q行,每行三个数字,x,y,z,表示将第x次操作中进行替换的第y个数字换成z。
对每次询问输出做出操作这种更改之后,m 次操作第一个人是否还能存在公司中。
逆向思维使查询和更新这个人的排名易于维护。(将rak定义为越大排名越靠前)
对于每个人的初始能力值其实我们只关心这个数字与第一个人能力值 k 的相对大小,
一开始可以根据每个人的初始能力值与m 次操作,建立每年这个人的rak值, rak越大表示排名越高
那么每次淘汰时,rak直接减去num,
并根据新加进来的值更新rak;
可以得到每年之后的rak数组a[ i ]。
但是询问中又涉及更改操作,我们需要知道询问做出更改之后,
对答案是否有贡献(是否引起rak值的变化),并且每次更改不独立,这次操作引起的rak值变化要持续到m年(区间更新)
每次查询时,询问的是有没有一个地方rak值小于等于0 。(如果在<m时出现小于等于0,那么就算m 年大于0也没啥用了。)
就是查询整个a[ i ]数组)
####好久没写过线段树了还挺亲切 ヽ(✿゚▽゚)ノ
int a[MAXN]; int n,m,k,q; vector<int>G[MAXN]; struct Segment_Tree { #define mid ((l+r)>>1) int minv[MAXN<<2],lazy[MAXN<<2]; #define lson rt<<1,l,((l+r)>>1) #define rson rt<<1|1,((l+r)>>1)+1,r inline int ls(int p) {return p<<1;} inline int rs(int p) {return p<<1|1;} void push_up(int p) {minv[p] = min(minv[ls(p)],minv[rs(p)]);} void push_down(int p) { minv[ls(p)]+=lazy[p]; minv[rs(p)]+=lazy[p]; lazy[ls(p)]+=lazy[p]; lazy[rs(p)]+=lazy[p]; lazy[p]=0; } void build(int rt,int l,int r) { lazy[rt]=0; if(l==r) {minv[rt]=a[l]; return ;} build(lson);build(rson);push_up(rt); } void update(int ql,int qr,int v,int rt,int l,int r)//区间更新 { if(ql>r||qr<l) return; if(ql<=l && qr>=r) {lazy[rt]+=v,minv[rt]+=v;return;} if(lazy[rt]!=0) push_down(rt); if(ql<=mid) update(ql,qr,v,lson); if(qr>mid) update(ql,qr,v,rson); push_up(rt); } #undef mid }tree; int main() { rd(n),rd(m),rd(q),rd(k); int rak=1; for(int i=2;i<=n;++i) { int x;rd(x); if(x<k) ++rak; } for(int i=1;i<=m;++i) { int num;rd(num); a[i]=rak-num;//去掉的肯定是比自己rak小的,所以排名降低 G[i].push_back(-1); for(int j=1;j<=num;++j) { int x;rd(x); G[i].push_back(x); if(x>k) --rak;// } } tree.build(1,1,m); while(q--) { int x,y,z;rd(x);rd(y);rd(z); if(x<m) { if(z>k&&k>G[x][y]) tree.update(x+1,m,-1,1,1,m); if(z<k&&k<G[x][y]) tree.update(x+1,m,1,1,1,m); } G[x][y]=z; printf("%d\n",tree.minv[1]>0); } //stop; return 0; }