一看到这道题我就想做线段树，好快写出来了，可是尼玛各种bug啊卧槽，后来搞了好久才解决 待会说下我的问题；唉还是太弱了；
struct Tree{
int type;
int po;
}tree[maxn<<2];po用来记录该节点是否被走过，type用来记录当前节点存储了多少颜色这里采用懒惰标记，当然 如果要往子节点继续找的话，懒惰标记下移，po=1表示被走过；
具体看代码；
在正常的update之后；还要把节点信息继续下移；下移的条件是，该节点被走过，也就是说子节点或更下面的节点有值，要更新到没被走过的那个节点；
具体看 newupdate函数；
void newupdate(int L,int R,int l,int r,int rt){
if(tree[rt].po==false)return;
if(tree[rt].type>0){
PushDown(rt);
}
int m = (l + r) >> 1; // 而如果你是要更新[1,1](必定访问到标记2) 那么先进行标记2 让两儿子的value更新
if (L <= m) newupdate(L , R , lson); //记得这时候儿子type被赋值，自己type=0;
if (R > m) newupdate(L , R , rson);
}最后用一个query函数来输出，输出的条件是当前节点的type>0 因为我们之前已经往下更新了；
最后记住输出的问题，我这里定义了一个全局变量first;初始化0只要准备输出之前让它++；只有first==1的时候输出type,不然前面要多输出一个空格
具体看代码
不过我这个程序居然跑了1400ms 感觉不够快，希望大牛们能够给予指点
#include <iostream>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define LL long long
const int maxn = 111111;
int first;
struct Tree{
int type;
int po;
}tree[maxn<<2];
void PushDown(int rt) {
if (tree[rt].type) {
tree[rt<<1].type += tree[rt].type;
tree[rt<<1|1].type += tree[rt].type ;
tree[rt].type = 0;
}
tree[rt].po=1;
}
void build(int l,int r,int rt) {
tree[rt].po=0;
tree[rt].type=0;
if (l == r){
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
}
void update(int L,int R,int c,int l,int r,int rt) {//(L,R)是我们要找的范围
if (L <= l && r <= R) {//标记1 //更新到这就行，不一定更新到最底端
tree[rt].type += c;
// tree[rt].value += c;
return ;
}
PushDown(rt );//延迟标记，这时候后推， (标记2)
int m = (l + r) >> 1;
if (L <= m) update(L , R , c , lson);
if (R > m) update(L , R , c , rson);
}
void newupdate(int L,int R,int l,int r,int rt){
if(tree[rt].po==false)return;
if(tree[rt].type>0){
PushDown(rt);
}
int m = (l + r) >> 1; // 而如果你是要更新[1,1](必定访问到标记2) 那么先进行标记2 让两儿子的value更新
if (L <= m) newupdate(L , R , lson); //记得这时候儿子type被赋值，自己type=0;
if (R > m) newupdate(L , R , rson);
}
void query(int L,int R,int l,int r,int rt) {
if(tree[rt].type>0){
for(int i=l;i<=r;i++){
first++;
if(first==1)cout<<tree[rt].type; //输出的处理
else
cout<<" "<<tree[rt].type; //输出的处理
}
}
else if(l==r&&tree[rt].type==0){
first++; //输出的处理
if(l==1)cout<<"0"; //输出的处理
else //输出的处理
cout<<" 0";} //输出的处理
else{
int m = (l + r) >> 1;
if (L <= m) query(L , R , lson);
if (R > m) query(L , R , rson);
}
}
int main() {
int n;int a,b;
while(cin>>n){
if(n==0)break;
first=0;
build( 1, n, 1);
for(int i=1;i<=n;i++){
cin>>a>>b;
update(a,b,1,1,n,1);
}
newupdate(1,n,1,n,1);
query(1,n,1,n,1);
cout<<endl;
}
return 0;
}
/*
*
6
1 2
3 4
1 4
2 4
3 5
2 2
2 4 4 4 1 0
*/
版权声明：本文为博主原创文章，未经博主允许不得转载。