题目链接：http://202.121.199.212/JudgeOnline/problem.php?id=1716
【题意】
1到N的区间，一种操作让编号从a到b的数变为z，但不会低于2，问多次操作后大于2的数减2后的和为多少。
【分析】
本来这题可以用线段树模拟过的，但是这里的N非常大，达到109，开个一维数组就会爆内存，更何况开个线段树。
分析题目后不难发现最后的一个操作一定生效，之前的操作如果有涉及之后操作区间的部分就会失效。根据这条性质，从操作的后面往前扫描，更新区间内的元素，如果元素被更新过就忽略，这样根据所有元素更新后的值就能算出结果了。如果用元素标记的方法一来时间复杂了，二来内存不够，所以绝对不能开一个一位数组来标记，也就是说这种方法不可行。
于是可以想到，把操作看成区间线段，从后往前坐做，每次只要更新之前未被区间覆盖到的元素，现在的问题是，区间可能交叉重叠，如何快速地判断区间是否已被覆盖？如果区间被之前的区间分为多个部分，如何区分？
以下为错误做法，但是AC了，数据太弱~
使用STL的MAP，map<int,int>表示 key之前的区间的元素值为value 。
对于每次的更新区间，处理其端点，二分查找与两个端点最近的且在右边的key值和相对应的value，来判断是否被覆盖，并更新。
假设依次处理红蓝绿三个区间，先查找与a、c相近的key，都没找到，就认为不存在覆盖,访问下map[a]，但值不动（如过之前没访问过就获得新值0，如果已经访问过，则保留原值，如果改变其值对端点重叠的情况会算错）；map[c]=value1。处理蓝色时b找到c，map[c]的值存在，所以b到c的区间是被覆盖的，不处理,map[e]=value2。 同理[d,e]被覆盖,map[f]=value3。这样就被分出3个有效区间[a,c]=value1、[c+1,e]=value2、[e+1,f]=value3。还有些细节处理下，这个算法就能AC题目了。
代码：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<int,long long> su;
int n,m;
struct node
{
int a,b,z;
void read()
{
scanf("%d%d%d",&a,&b,&z);
}
}data[];
int main ()
{
while (~scanf("%d",&n))
{
su.clear();
scanf("%d",&m);
for (int i=;i<m;++i)
data[i].read();
for (int i=m-;i>=;--i)
{
map<int,long long>::iterator p1=su.upper_bound(data[i].a);
map<int,long long>::iterator p2=su.upper_bound(data[i].b);
int pp1,pp2;
long long v1,v2;
if (p1==su.end()) pp1=-; else {pp1=p1->first;v1=su[pp1];}
if (p2==su.end()) pp2=-; else {pp2=p2->first;v2=su[pp2];} if (pp1==- || v1<=)
{
//cout<<su[data[i].a]<<endl;
su[data[i].a];
if (pp1!=- && data[i].b+>pp1)su[pp1]=data[i].z; //这里特殊区间要判断排除下
}
if (pp2==- || v2<=)
{
su[data[i].b+]=data[i].z;
} }
long long sum=;
map<int,long long>::iterator i=su.begin();
//cout<<i->first<<" "<<i->second<<endl;
int pp=i->first;
++i;
for (;i!=su.end();++i)
{
if (i->second>=)
{
// cout<<i->first<<" "<<i->second<<endl;
int tem=i->first;
if (tem>n+) tem=n+;
sum+=(long long )(i->second-)*(long long)(tem-pp);
}
pp=i->first;
}
cout<<sum<<endl;
}
}
用map时要注意，只要访问修改过map的元素，原先的迭代器就有可能失效！
这种用map的算法因为用key的大小关系来标记线段,所以不仅可以标记离散的区间，还可以来标记连续的空间: map<double,int>,很是强大。
很可惜以上是错误的算法，因为有种情况该算法无法解决，那就是区间被之前的区间分为多个部分，该算法最多只能分出两部分，有的区间就漏了！
《正确做法》：
最朴素的做法，直接从前往后，对每个区间进行染色，这样就能覆盖老的值，现在只要加快区间染色速度就好。
做法和以上类似，用map<int,int>表示 key之前的区间的元素值为value，只是为了要覆盖原来的区间，所以要删除在现在区间内的所有key，这个二分查找上下界就好了。
class Intervals {
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
Intervals() {
map.put(Integer.MIN_VALUE, 0);
map.put(Integer.MAX_VALUE, 0);
}
void paint(int s, int t, int c) {
int p = get(t);
map.subMap(s, t).clear(); /******/
map.put(s, c);
map.put(t, p);
}
int get(int k) {
return map.floorEntry(k).getValue();
}
long getAns(int n) {
long ans = 0;
for (int i = 1; i <= n; ) {
long v = get(i);
int r = map.higherKey(i);
ans += v * (r - i);
i = r;
}
return ans;
}
}