http://codevs.cn/problem/1217/
唉。。。即使是以我四年后的水平也要改一遍。。。
太菜了。。。
应该是目前最常用的线段树写法。。。确实是能过的

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e6;
int lazy[4*N],mv[4*N];
void read(int &x)
{
char c=getchar();
x=0;
while (!(c>='0'&&c<='9'||c=='-')) c=getchar();
int f=0;
if (c=='-') {
f=1;
c=getchar();
}
while (c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
if (f) x=-x;
}
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
void push_up(int rt)
{
mv[rt]=min(mv[rt<<1],mv[rt<<1|1]);
}
void build(int l,int r,int rt)
{
if (l==r) {
read(mv[rt]);
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
push_up(rt);
}
void push_down(int rt)
{
lazy[rt<<1]+=lazy[rt];
mv[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
mv[rt<<1|1]+=lazy[rt];
lazy[rt]=0;
}
bool update(int l,int r,int rt,int L,int R,int del)
{
if (L<=l&&r<=R) {
lazy[rt]+=del;
mv[rt]+=del;
if (mv[rt]<0) return false;
else return true;
}
push_down(rt);
int m=(l+r)>>1;
bool res=true;
if (L<=m) res&=update(lson,L,R,del);
if (!res) return false;
if (m<R) res&=update(rson,L,R,del);
push_up(rt);
return res;
}
int n,m;
int check()
{
for (int i=1; i<=m; i++) {
int d,s,t;
read(d);
read(s);
read(t);
if (!update(1,n,1,s,t,-d)) return i;
}
return m+1;
}
int main()
{
read(n);
read(m);
build(1,n,1);
int ans=check();
if (ans>m) puts("0");
else printf("-1\n%d\n",ans);
return 0;
}

下面介绍一种据说是正解的方法(不超纲的方法):
二分答案,判断的时候用差分的思想。
差分……差分你懂吧?

好巧啊,我也不懂……
引用一下别人的解释:

懂了吧……

mdzz 看代码吧!

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int n,m;
int a[N],s[N],t[N],d[N],mk[N];
void read(int &x)
{
char c=getchar();
x=0;
while (!(c>='0'&&c<='9'||c=='-')) c=getchar();
int f=0;
if (c=='-') {
f=1;
c=getchar();
}
while (c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
if (f) x=-x;
}
bool check(int x)
{
memset(mk,0,sizeof(mk));
for (int i=1;i<=x;i++)
mk[s[i]]+=d[i],mk[t[i]+1]-=d[i];
for (int i=1,sum=0;i<=n;i++){
sum+=mk[i];
if (sum>a[i]) return false;
}
return true;
}
int solve()
{
int l=1,r=m+1;
while (l<r){
int m=(l+r)>>1;
if (!check(m)) r=m;
else l=m+1;
}
return r;
}
int main()
{
read(n);
read(m);
for (int i=1;i<=n;i++)
read(a[i]);
for (int i=1;i<=m;i++)
read(d[i]),read(s[i]),read(t[i]);
int ans=solve();
if (ans>m) puts("0");
else printf("-1\n%d\n",ans);
return 0;
}

线段树的复杂度是 O(MlogN)
二分答案+差分的复杂度是 O(NlogM)
【其实一样
当然线段树常数肯定大一点,比赛的时候也有很多人线段树没满分。
不得不说 NOIP 确实是希望你巧妙的解题的。。。

最后再推荐一下 codevs 。。。
大家公认的界面领先 OJ 界至少3年 ←_←
还有一个原因就是。。。对蒟蒻比较友好。。。

=========2018/02/22=========
codevs 太凉了,推荐一下洛谷,贼6好吧