poj 2777（线段树的节点更新策略）

/*

之前的思想是用回溯的方式进行颜色的更新的！如果用回溯的方法的话，就是将每一个节点的颜色都要更新

通过子节点的颜色情况来判断父节点的颜色情况 ！这就是TLE的原因！

后来想一想没有必要 ！加入[a, b] 区间有p管辖，那么tree[p]的颜色值就是[a, b]所有点的颜色值！

如果[a,b]的子区间[c,d]没被跟新，那么tree[p]也是[c,d]的值！

否则，在更新[c,d]区间的时候，一定会经过 p 点！然后由上到下更新p 1 和 p 1|1 的值!

当找到[c,d]区间所对应的p‘时，并更新p’的值！、

之前的剪枝是点返回， 后面的是线段返回，当然更快！ 

#include string 

#include iostream 

#include algorithm 

#include cstring 

#include cstdio 

#define M 100005 

using namespace std;


void updateT(int ld, int rd, int a, int b, int p, int k){

 if(tree[p] == k) return ;//如果当前更新的颜色和 之前p所管辖的区间的颜色相同，则返回 

 if(ld==a rd==b){//p所管辖的区间的点的颜色全部是k！如果其子区间的颜色被更改，那么 

 tree[p]=k; //在更新子区间的时候一定会经过 p点，让后通过p更新 p 1 和 p 1|1 子区间的颜色！ 

 return ;

 if(tree[p]!=-1){//也就是在经过父节点时更新子节点的颜色状态，也就是[a,b]包含在 p点所管辖的区间内 

 tree[p 1] = tree[p 1|1] = tree[p];

 tree[p]=-1;

 if(ld rd){

 int mid = (ld+rd)/2;

 if(mid a)

 updateT(mid+1, rd, a, b, p 1|1, k);

 else if(mid =b)

 updateT(ld, mid, a, b, p 1, k);

 else{

 updateT(ld, mid, a, mid, p 1, k);

 updateT(mid+1, rd, mid+1, b, p 1|1, k);

void queryT(int ld, int rd, int a, int b, int p){

 if(ld rd) return ;

 if(tree[p]!=-1){

 color[tree[p]]=1; 

 else{

 int mid = (ld+rd)/2;

 if(mid a)

 queryT(mid+1, rd, a, b, p 1|1);

 else if(mid =b)

 queryT(ld, mid, a, b, p 1);

 else{

 queryT(ld, mid, a, mid, p 1);

 queryT(mid+1, rd, mid+1, b, p 1|1);

int main(){

 while(scanf("%d%d%d", L, T, O)!=EOF){

 buildT(1, L, 1);

 while(O--){

 char ch[2];

 int a, b, c;

 scanf("%s", ch);

 if(ch[0]==C){

 scanf("%d%d%d", a, b, 

 if(a b){

 a^=b;

 b^=a;

 a^=b; 

 updateT(1, L, a, b, 1, c);

 else{

 scanf("%d%d", a, 

 if(a b){

 a^=b;

 b^=a;

 a^=b; 

 memset(color, 0, sizeof(color));

 queryT(1, L, a, b, 1); 

 int cnt=0;

 for(int i=1; i ++i)

 if(color[i]) ++cnt;

 printf("%d\n", cnt);

 return 0;

}

刷爆 LeetCode 周赛 337，位掩码/回溯/同余/分桶/动态规划·打家劫舍/贪心 上周末是 LeetCode 第 337 场周赛，你参加了吗？这场周赛第三题有点放水，如果按照题目的数据量来说最多算 Easy 题，但如果按照动态规划来做可以算 Hard 题。
一道线段树相关算法题 每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。