Problem A
内存限制 256MB 时间限制 5S
程序文件名 A.pas/A.c/A.cpp
输入文件 A.in 输出文件 A.out
你有一片荒地，为了方便讨论，我们将这片荒地看成一条直线，这条直线被划分成n段（从左往右，依次标为1,2,3,...,n）。
接下来的m年，你会开垦这片荒地并种植作物。不过每年的播种都会受到限制，如果你选择这一年播种，你必须将某段区间全部播种，并且也只能在这段区间播种。
不过，荒地本身并不适合种植，所以你需要对土地花一定成本改良土质才能播种，而改良过的土地就不需要再次改良了。因此有时候播种可能不是很明智，你也可以选择这一年不播种。
现在你想知道自己通过这m年种植最多能赚到多少钱。
输入
第一行，两个整数 n,m
第二行，n个整数
依次代表每段土地改良土质的花费(标号从1到n)
接下来有m行，每行代表1年的播种情况(从第一年到第m年)
每行有3个整数，l,r,p (1<=l<=r<=n)
依次是这一年播种区间的左边界和右边界的编号，以及这次播种收获的作物能卖出的价钱
输出
一行，一个整数，代表最大的利润
样例输入
7 4
3 2 3 2 1 2 3
1 2 5
2 3 5
3 5 3
7 7 5
样例输出
4
数据范围
30% n,m<=100
100% n,m<=200000
其他输入的整数均为不超过 1000 000 000 的正整数
DP里面我就是最怕这样的题，在考场上由于用的是最大权闭合子图，根本没往DP方面想。而且这道题DP的优化也是我在用裸的DP编了一遍后才看出来的。注意到DP转移中只存在赋值，区间最值，区间加这几个操作，着表示可以用线段树整体维护。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#define MAXN 1100000
#define MAXM 1000000
#define MAXT 1000000
#define lch (now<<1)
#define rch (now<<1^1)
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define PROB "A"
typedef long long qword;
struct aaa
{
int x,y,z;
}al[MAXM];
bool operator< (aaa a1,aaa a2)
{
return a1.x<a2.x||(a1.x==a2.x && a1.y<a2.y);
}
int n,m;
//qword f[MAXN];
int value[MAXN];
qword sum[MAXN];
//segment tree
struct node
{
int l,r;
qword val1,val2,lazy;
}tree[MAXT];
inline void up(int now)
{
if (tree[now].l==tree[now].r)return ;
tree[now].val1=max(tree[lch].val1,tree[rch].val1)+tree[now].lazy;
tree[now].val2=max(tree[lch].val2,tree[rch].val2)+tree[now].lazy;
}
inline void down(int now)
{
if (tree[now].l==tree[now].r)return ;
tree[lch].lazy+=tree[now].lazy;
tree[lch].val1+=tree[now].lazy;
tree[lch].val2+=tree[now].lazy;
tree[rch].lazy+=tree[now].lazy;
tree[rch].val1+=tree[now].lazy;
tree[rch].val2+=tree[now].lazy;
tree[now].lazy=;
}
void build_tree(int now,int l,int r)
{
tree[now].l=l;
tree[now].r=r;
tree[now].lazy=;
if (l==r)
{
tree[now].val1=-INFL;
tree[now].val2=-INFL;
if (!l)
{
tree[now].val1=tree[now].val2=;
}
return ;
}
build_tree(lch,l,(l+r)>>);
build_tree(rch,((l+r)>>)+,r);
up(now);
}
void set_val(int now,int pos,qword v,qword vnow)
{
if (tree[now].l==tree[now].r)
{
if (v>vnow+tree[now].val1)
{
tree[now].val1=v-vnow;
tree[now].val2=v-vnow+sum[tree[now].l];
}
return ;
}
if (pos<=(tree[now].l+tree[now].r)>>)
set_val(lch,pos,v,vnow+tree[now].lazy);
else
set_val(rch,pos,v,vnow+tree[now].lazy);
up(now);
}
qword get_val1(int now,int l,int r)
{
if (l>r)return -INFL;
if (tree[now].l==l && tree[now].r==r)
{
return tree[now].val1;
}
int mid=(tree[now].l+tree[now].r)>>;
if (r<=mid)
return get_val1(lch,l,r)+tree[now].lazy;
if (mid<l)
return get_val1(rch,l,r)+tree[now].lazy;
return max(get_val1(lch,l,mid),get_val1(rch,mid+,r))+tree[now].lazy;
}
qword get_val2(int now,int l,int r)
{
if (l>r)return -INFL;
if (tree[now].l==l && tree[now].r==r)
{
return tree[now].val2;
}
int mid=(tree[now].l+tree[now].r)>>;
if (r<=mid)
return get_val2(lch,l,r)+tree[now].lazy;
if (mid<l)
return get_val2(rch,l,r)+tree[now].lazy;
return max(get_val2(lch,l,mid),get_val2(rch,mid+,r))+tree[now].lazy;
}
void add_val(int now,int l,int r,qword v)
{
if (tree[now].l==l && tree[now].r==r)
{
tree[now].lazy+=v;
tree[now].val1+=v;
tree[now].val2+=v;
return ;
}
int mid=(tree[now].l+tree[now].r)>>;
down(now);
if (r<=mid)
{
add_val(lch,l,r,v);
return up(now);
}
if (mid<l)
{
add_val(rch,l,r,v);
return up(now);
}
add_val(lch,l,mid,v);
add_val(rch,mid+,r,v);
return up(now);
}
void scan(int now,qword vnow)
{
if (tree[now].l==tree[now].r)
{
printf("%lld ",vnow+tree[now].val1);
return ;
}
scan(lch,vnow+tree[now].lazy);
scan(rch,vnow+tree[now].lazy);
}
int main()
{
freopen(PROB".in","r",stdin);
// freopen("4.in","r",stdin);
freopen(PROB".out","w",stdout);
int i;
scanf("%d%d",&n,&m);
sum[]=;
for (i=;i<=n;i++)
{
scanf("%d",&value[i]);
sum[i]=sum[i-]+value[i];
}
int j;
for (i=;i<m;i++)
{
scanf("%d%d%d",&al[i].x,&al[i].y,&al[i].z);
}
sort(al,&al[m]);
/*for (i=0;i<m;i++)
{
for (j=al[i].y;j<=n;j++)
{
f[j]=max(f[j],f[j]+al[i].z);
}
for (j=al[i].x;j<al[i].y;j++)
{
f[al[i].y]=max(f[al[i].y],f[j]-(sum[al[i].y]-sum[j])+al[i].z);
}//f[j]+sum[j] -sum[al[u].y]+al[i].z
for (j=0;j<al[i].x;j++)
{
f[al[i].y]=max(f[al[i].y],f[j]-(sum[al[i].y]-sum[al[i].x-1])+al[i].z);
}
}*/
//for (i=1;i<=n+2;i++)f[i]=-INFL;
//f[0]=0;
build_tree(,,n);
for (i=;i<m;i++)
{
add_val(,al[i].y,n,al[i].z);
set_val(,al[i].y,get_val2(,al[i].x,al[i].y-)-sum[al[i].y]+al[i].z,);
set_val(,al[i].y,get_val1(,,al[i].x-)-(sum[al[i].y]-sum[al[i].x-])+al[i].z,);
//scan(1,0);printf("\n");
/* for (j=al[i].y;j<=n;j++)
{
f[j]=max(f[j],f[j]+al[i].z);
}
for (j=al[i].x;j<al[i].y;j++)
{
f[al[i].y]=max(f[al[i].y],f[j]-(sum[al[i].y]-sum[j])+al[i].z);
}//f[j]+sum[j] -sum[al[u].y]+al[i].z
for (j=0;j<al[i].x;j++)
{
f[al[i].y]=max(f[al[i].y],f[j]-(sum[al[i].y]-sum[al[i].x-1])+al[i].z);
}
for (j=0;j<=n;j++)
{
printf("%lld ",f[j]);
}printf("\n");*/
}
/*qword ans=0;
for (i=0;i<=n;i++)
{
printf("%d ",f[i]);
ans=max(ans,f[i]);
}*/
qword ans2=get_val1(,,n);
printf("%lld\n",ans2);
return ;
}