题意： 现有一个公司，初始有n个员工。有m年，第i年裁员Ri个人，新增Ri个员工。每个员工都有一个能力值，裁员时选择能力值最低Ri个的裁。保证能力值互不相同。有k次会累计的修改。将第x年新进的第y名员工的能力值改为z。主角是初始1号员工。问：在k次修改后，主角能不能坚持m年不被裁。
题解： 首先明确一点，如果一个人的能力值改前和改后与1号员工的的能力值的相对大小不变。则此后所有的裁员，1号员工则不受影响。 粗略证明： 首先明确，如果当前有x名员工比1号低，y名员工比1号高，则无论这x，y名员工的能力值大小如何变换，都不影响1号员工被裁与不被裁的结果。而且裁员后1号的排名不会变化（即使1号被裁，1号员工也会有一个总排位）。 试想，如果当前有x名员工比1号低，y名员工比1号高，现在一名员工的能力值发生修改。但是他的能力值改前和改后与1号员工的的能力值的相对大小不变。那么显然x，y的值不发生变化。则不影响1号员工被裁与不被裁的结果。而且裁员后1号的排名不会变。所以经过此次裁员后，比一号低的和高的数量不会发生变化。有变成一个与当前等价的子状态。所以此后的裁员都不收影响（数学归纳法）。
现在我们不妨先不裁员，只加人。 而现在如果一个员工修改之前和之后与1号员工的的能力值的相对大小发生改变，则1号员工的在此后的排位都会+1或-1。而此时1号能不能在一次裁员中留下了，取决与该次裁员留下的人数，如果员工排位高于留下的人数就不会被裁。
显然我们先搞出m年每一年的1号员工不裁员只加人的排位。然后线段数维护序列（该年留下的人数-该年1号点排位）对于每次修改，如果这次修改改变了与1的相对大小，则在此后的裁员都让序列+1或-1。如果序列中没有负数，则1号员工可以留下来。 下面是ac代码
#include<cstdio> #include<iostream> #include<cstring> #include <map> #include <queue> #include <set> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <list> #include <bitset> #include <array> #include <cctype> #include <time.h> #pragma GCC optimize(2) void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); } void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); } void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; } template <typename T> bool bacmp(const T & a, const T & b) { return a > b; } template <typename T> bool pecmp(const T & a, const T & b) { return a < b; } #define ll long long #define ull unsigned ll #define _min(x, y) ((x)>(y)?(y):(x)) #define _max(x, y) ((x)>(y)?(x):(y)) #define max3(x, y, z) ( max( (x), max( (y), (z) ) ) ) #define min3(x, y, z) ( min( (x), min( (y), (z) ) ) ) #define pr(x, y) (make_pair((x), (y))) #define pb(x) push_back(x); using namespace std; const int N = 2e5 + 5; struct Node { int l, r; int laz; int mi; } tr[N<<4]; int pai[N]; void build (int p, int l, int r) { tr[p].l = l; tr[p].r = r; tr[p].laz = 0; if (l == r) {tr[p].mi = pai[l]; return;} int mid = (l + r) >> 1; build(p<<1, l, mid); build(p<<1|1, mid+1, r); tr[p].mi = min(tr[p<<1].mi, tr[p<<1|1].mi); } inline void update(int p, int v) { tr[p].mi += v; tr[p].laz += v; } inline void spread(int p) { if (tr[p].laz == 0) return; update(p<<1, tr[p].laz); update(p<<1|1, tr[p].laz); tr[p].laz = 0; } void change(int p, int l, int r, int z) { if (l > r) return; if (l <= tr[p].l && tr[p].r <= r) { update(p, z); return; } spread(p); int mid =(tr[p].l + tr[p].r) >> 1; if (l <= mid) change(p<<1, l, r, z); if (r > mid) change(p<<1|1, l, r, z); tr[p].mi = min(tr[p<<1].mi, tr[p<<1|1].mi); } vector<int> q[N]; int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); int _rank = 1; int g = 1; for (int i = 1; i <= n; i++) { int te; scanf("%d", &te); if (i == 1) g = te; else _rank += te > g; } for (int i = 1; i <= m; i++) { pai[i] = _rank; int k; scanf("%d", &k); while(k--) { int te; scanf("%d", &te); q[i].pb(te); _rank += te > g; } pai[i] = (n - q[i].size()) - pai[i]; } build(1, 1, m); for (int i = 1; i <= k; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); y--; int yu = q[x][y]; if (yu < g && g < z) change(1, x+1, m, -1); else if (z < g && g < yu) change(1, x+1, m, 1); puts(tr[1].mi >= 0 ? "1" : "0"); q[x][y] = z; } return 0; }