题干：
本题保证 mm 个区间两两不相交。
小 P 得到了一个长为 nn 的序列，序列元素编号 1…n1…n。小 P 想给这个序列的每个元素染上黑 白两种颜色之一，于是他就随便制定了一个染色方案。正当小 P 要染色时，小 A 批判道：“Naive！这个染色方案太难看了，你应该仔细分析染色的效果之后再动手。” 小 A 和小 P 一起分析序列的性质之后，得出两个结论：
- 序列中的第 ii 个位置染成黑色会产生 bibi 的美感，染成白色会产生 wiwi 的美感。
- 有些区间比较特殊，如果区间内的所有数都染成黑色会额外得到 cici 的美感；另一些区间则恰好相反，如果区间内的所有数都染成白色会额外得到 cici 的美感。
小 A 和小 P 想知道美感总和的最大值，请你帮他们求出这个值。
输入格式
第一行两个整数 n,mn,m，分别表示序列的长度和特殊区间的数量。
第二行 nn 个整数 bibi，表示每个位置染成黑色会得到的美感。
第三行 nn 个整数 wiwi，表示每个位置染成白色会得到的美感。
接下来下 mm 行，每行四个整数 ti,li,ri,citi,li,ri,ci。 ti=1ti=1 表示如果区间 [li,ri][li,ri] 都被染成黑色会额外得到 cici 的美感， ti=2ti=2 则表示如果区间 [li,ri][li,ri] 都被染成白色会额外得到 cici 的美感。
输出格式
输出一行一个整数，表示美感总和的最大值。
数据范围与约定
保证 0≤n,m≤3×105,1≤li≤ri≤n,?109≤wi,bi≤109,ti∈{1,2},1≤ci≤1090≤n,m≤3×105,1≤li≤ri≤n,?109≤wi,bi≤109,ti∈{1,2},1≤ci≤109 。
本题保证 mm 个区间两两不相交。
Sample Input
5 2 1 2 2 4 3 0 -2 7 1 5 2 1 2 7 1 5 5 1
Sample Output
21
Sample Explain
第 44 个位置染成黑色，其余位置染成白色，得到美感总和为 0+(?2)+7+4+5+7=210+(?2)+7+4+5+7=21。
分析：
简单动归，用map存放特殊区间相关数据，key为r（右界），value为数组，数组中存放l（左界）、c（额外分）、count（区间填同一色的总分，填何种颜色按照t的值判断），ans数组维护前i个元素染色的最高分。
转移方程为
ans[i]=max(ans[i-1]+b[i],ans[i-1]+w[i]);
ans[i]=max(ans[iter->second[0]-1]+iter->second[1]+iter->second[2],ans[i]); （i在r上的额外情况考虑）
题解：
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
int main(){
ll n,m;
cin>>n>>m;
ll b[n+7];
ll w[n+7];
for(ll i=1;i<=n;++i){
cin>>b[i];
}
for(ll i=1;i<=n;++i){
cin>>w[i];
}
map<ll,vector<ll> > hashmap;
map<ll,vector<ll> >::iterator iter;
for(ll i=1;i<=m;++i){
ll t,l,r,c;
cin>>t>>l>>r>>c;
vector<ll> v;
v.push_back(l);
v.push_back(c);
ll count=0;
if(t==1){
for(ll j=l;j<=r;++j){
count+=b[j];
}
}
else{
for(ll j=l;j<=r;++j){
count+=w[j];
}
}
v.push_back(count);
hashmap.insert(make_pair(r,v));
}
ll ans[n+7];
memset(ans,0,sizeof(ans));
ans[1]=max(b[1],w[1]);
iter=hashmap.find(1);
if(iter!=hashmap.end()){
ans[1]+=iter->second[1];
}
for(ll i=2;i<=n;++i){
ans[i]=max(ans[i-1]+b[i],ans[i-1]+w[i]);
iter=hashmap.find(i);
if(iter!=hashmap.end()){
ans[i]=max(ans[iter->second[0]-1]+iter->second[1]+iter->second[2],ans[i]);
}
}
cout<<ans[n];
return 0;
}