还是一道整体二分的题目，思路和之前的类似就不再赘述了恩！
注意是一个环所以修改的时候要讨论一下
1 /************************************************************** 2 Problem: 2527 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:10760 ms 7 Memory:33508 kb 8 ****************************************************************/ 9 10 #include11 #include 12 #include 13 14 using namespace std; 15 typedef long long ll; 16 const int N = 3e5 + 5; 17 const ll inf = 1e9; 18 const int Maxlen = 5 * N * 10; 19 20 int n, m, k, time; 21 int p[N], w[N], t[N], ans[N]; 22 int l[N], r[N], v[N]; 23 vector a[N]; 24 ll BIT[N]; 25 bool vis[N]; 26 27 char buf[Maxlen], *c = buf; 28 int Len; 29 30 inline int read() { 31 int x = 0; 32 while (*c < '0' || '9' < *c) ++c; 33 while ('0' <= *c && *c <= '9') 34 x = x * 10 + *c - '0', ++c; 35 return x; 36 } 37 38 #define lowbit(x) x & -x; 39 inline void add(int x, int d) { 40 while (x <= m) 41 BIT[x] += d, x += lowbit(x); 42 } 43 44 inline ll query(int x) { 45 ll res = 0; 46 while (x) 47 res += BIT[x], x -= lowbit(x); 48 return res; 49 } 50 #undef lowbit 51 52 inline void Add(int x, int d) { 53 if (l[x] <= r[x]) 54 add(l[x], d * v[x]), add(r[x] + 1, d * (-v[x])); 55 else 56 add(1, d * v[x]), add(r[x] + 1, d * (-v[x])), add(l[x], d * v[x]); 57 } 58 59 void work(int l, int r, int L, int R) { 60 if (l > r) return; 61 if (L == R) { 62 int i; 63 for (i = l; i <= r; ++i) 64 ans[w[i]] = L; 65 return; 66 } 67 int mid = L + R >> 1, cntl = 0, now, i, j, l1, l2; 68 ll tot; 69 while (time <= mid) Add(++time, 1); 70 while (time > mid) Add(time--, -1); 71 for (i = l; i <= r; ++i) { 72 now = w[i]; 73 for (j = tot = 0; j < a[now].size(); ++j) 74 if ((tot += query(a[now][j])) >= p[now]) break; 75 if (tot >= p[now]) vis[now] = 1, ++cntl; 76 else vis[now] = 0; 77 } 78 for (i = l1 = l, l2 = l + cntl; i <= r; ++i) 79 if (vis[w[i]]) t[l1++] = w[i]; 80 else t[l2++] = w[i]; 81 for (i = l; i <= r; ++i) w[i] = t[i]; 82 work(l, l1 - 1, L, mid), work(l1, r, mid + 1, R); 83 } 84 85 86 int main() { 87 Len = fread(c, 1, Maxlen, stdin); 88 buf[Len] = '\0'; 89 int i; 90 n = read(), m = read(); 91 for (i = 1; i <= m; ++i) 92 a[read()].push_back(i); 93 for (i = 1; i <= n; ++i) 94 p[i] = read(), w[i] = i; 95 k = read(); 96 for (i = 1; i <= k; ++i) 97 l[i] = read(), r[i] = read(), v[i] = read(); 98 ++k, l[k] = 1, r[k] = m, v[k] = inf; 99 work(1, n, 1, k);100 for (i = 1; i <= n; ++i)101 if (ans[i] != k) printf("%d\n", ans[i]);102 else puts("NIE");103 return 0;104 }