Link
考虑朴素算法，循环$K$次，每次循环$1$到$N$增加相应的$[L,R,A]$，然后$O(N)$判断某一个数是不是已经合法。这样的算法的时间复杂度是$O(N^3)$，那么我们考虑逐步优化。
- 首先区间加我们肯定可以使用线段树或者树状数组，这里使用的是后者。
- 改换一下枚举顺序就可以变成先枚举每一个数，然后枚举$K$次，然后我们发现枚举$K$次的这个步骤是单调的，因为对于某一个数，如果在$X$次区间加之后没有合法，那么在之前肯定也是不合法的，如果在$X$次区间加之后是合法的，那么在这之后肯定也是合法的，所以这个枚举$K$的步骤是单调的，于是可以考虑二分答案。
那么总步骤就得出来了：- 枚举每一个位置
- 二分区间加的次数
- 树状数组区间加
总时间复杂度$O(Nlog^2N)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
using namespace std ;
const unsigned long long Inf = 0x7fffffff ;
const unsigned long long MAXN = 300010 ;
const unsigned long long MAXM = 300010 ;
unsigned long long N, M, Sta[MAXN], Data[MAXN], W[MAXN], Now, K ;
vector <unsigned long long> H[MAXN] ; unsigned long long Tot[MAXN] ;
unsigned long long LSum[MAXN], RSum[MAXN], Sum[MAXN], Ans[MAXN] ;
struct Node {
unsigned long long L, R, V ;
} E[MAXN << 1] ;
inline unsigned long long Read() {
unsigned long long X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
inline unsigned long long Lowbit(unsigned long long Now) { return Now & (- Now) ; }
inline void Add(unsigned long long Now, unsigned long long K) {
while (Now <= M) {
Sum[Now] += K ;
Now += Lowbit(Now) ;
} return ;
}
inline unsigned long long Query(unsigned long long Now) {
unsigned long long Ans = 0 ;
while (Now) {
Ans += Sum[Now] ;
Now -= Lowbit(Now) ;
} return Ans ;
}
inline void Change(unsigned long long Now, unsigned long long L, unsigned long long R) {
if (L <= R) Add(L, Now), Add(R + 1, - Now) ;
if (L > R) Add(1, Now), Add(R + 1, - Now) ,
Add(L, Now), Add(M + 1, - Now) ;
}
inline void Erfen(unsigned long long L, unsigned long long R, unsigned long long U, unsigned long long D) {
//out << L << " " << R << " " << U << " " << D << endl ;
unsigned long long Mid = (L + R) >> 1 ;
if (L == R) {
for (unsigned long long i = U ; i <= D ; i ++) Ans[W[i]] = L ;
return ;
}
while (Now < Mid)
Now ++, Change(E[Now].V, E[Now].L, E[Now].R) ;
while (Now > Mid)
Change(- E[Now].V, E[Now].L, E[Now].R), Now -- ;
for (unsigned long long i = U ; i <= D ; i ++) {
Tot[W[i]] = 0 ;
for (unsigned long long j = 0 ; j < H[W[i]].size() ; j ++)
Tot[W[i]] += Query(H[W[i]][j]) ;
}
unsigned long long LL = 0, RR = 0 ;
for (unsigned long long i = U ; i <= D ; i ++)
if (Tot[W[i]] >= Data[W[i]])
LSum[++ LL] = W[i] ;
else RSum[++ RR] = W[i] ;
for (unsigned long long i = 1 ; i <= LL ; i ++)
W[i + U - 1] = LSum[i] ;
for (unsigned long long i = 1 ; i <= RR ; i ++)
W[U + LL + i - 1] = RSum[i] ;
Erfen(L, Mid, U, U + LL - 1) ;
Erfen(Mid + 1, R, U + LL, D) ;
}
int main() {
N = Read(), M = Read() ;
for (unsigned long long i = 1 ; i <= M ; i ++)
Sta[i] = Read(), H[Sta[i]].push_back(i) ;
for (unsigned long long i = 1 ; i <= N ; i ++)
Data[i] = Read(), W[i] = i ;
K = Read() ;
for (unsigned long long i = 1 ; i <= K ; i ++)
E[i].L = Read(), E[i].R = Read(), E[i].V = Read() ;
E[K + 1].L = 1, E[K + 1].R = M, E[K + 1].V = Inf, Now = 0 ;
Erfen(1, K + 1, 1, N) ;
for (unsigned long long i = 1 ; i <= N ; i ++) {
if (Ans[i] == K + 1) printf("NIE\n") ;
else printf("%lld\n", Ans[i]) ;
}
return 0 ;
}