首页 > 代码库 > hdu--4339--线段树

hdu--4339--线段树

很多时候  平常觉得很熟悉的一样东西穿上了一件外衣 我们就不认识了  

其实 还是 我们不够熟悉。

这题的原型 就是给你一串由01组成的序列 可以随机修改某个固定位置的值<由0变1 由1变0> 然后就是要让我们求出从某个 x的左端点开始的最长连续1的数量

我们将这题 转换过来 就是对应坐标位置 假如2个值相同则为1 否则为0 然后我们每次的修改某个字符串的字符 也会对于该位置对应的序列值可能会发生变化 不一定 看具体修改情况

询问的话 就是刚刚说的 从x这个端点向右连续1的数量 当然包括它本身

这边 我觉得需要注意一点

tree[rt].Lson/Rson  你这边的Lson Rson都是指 rt所表示的区间下 从它的左边端点 与 右边端点出发的 连续1的数量

所以 假如我们存在查询的端点值x位于 rt<<1 就是rt的左子区间下 那我们就要注意判断了 如果这时候你的左子区间满足从左子区间右边数过来连续1的数量到底的坐标是<=L的

那么 我们在统计从x开始向右的连续1的数量的时候就应该继续是统计左子区间的同时还要加上右子区间 至于 右子区间具体有没有就看函数自己执行下去了 反正我们指令发出去了

但假如查询的x位于 rt<<1|1 就是rt的右子区间下 那就不需要那么麻烦了  就对于当前rt所表示的区间而言 rt<<1|1已经是最右边了  但是rt<<1|1可能它自身在进行判断的时候又会遇到刚刚的情况 x 位于 ( rt<<1|1)<<1 它的左子区间下 那就重复上面操作 就好了

 

单点更新 区间求值

  1 #include <iostream>  2 #include <cstring>  3 #include <algorithm>  4 using namespace std;  5   6 const int size = 1000010;  7 int len;  8 char ss[size] , tt[size];  9 int num[size]; 10 struct node 11 { 12     int L , R , Len; 13     int Lone , Rone; 14 }tree[size*4]; 15  16 void init( ) 17 { 18     len = min( strlen(ss) , strlen(tt) ); 19     memset( num , 0 , sizeof(num) ); 20     for( int i = 0 ; i<len ; i++ ) 21     { 22         if( ss[i]==tt[i] ) 23             num[i+1] = 1; 24     } 25 } 26  27 void pushUp( int rt ) 28 { 29     tree[rt].Lone = tree[rt<<1].Lone; 30     tree[rt].Rone = tree[rt<<1|1].Rone; 31     if( tree[rt<<1].Lone == tree[rt<<1].Len ) 32         tree[rt].Lone += tree[rt<<1|1].Lone; 33     if( tree[rt<<1|1].Rone == tree[rt<<1|1].Len ) 34         tree[rt].Rone += tree[rt<<1].Rone; 35 } 36  37 void build( int rt , int L , int R ) 38 { 39     int M = ( L + R ) >> 1; 40     tree[rt].L = L; 41     tree[rt].R = R; 42     tree[rt].Len = R - L + 1; 43     if( L==R ) 44     { 45         tree[rt].Lone = tree[rt].Rone = num[L]; 46         return ; 47     } 48     build( rt<<1 , L , M ); 49     build( rt<<1|1 , M+1 , R ); 50     pushUp( rt ); 51 } 52  53 void update( int rt , int L , int var ) 54 { 55     int M = ( tree[rt].L + tree[rt].R ) >> 1; 56     if( tree[rt].L == L && tree[rt].R == L ) 57     { 58         tree[rt].Lone = tree[rt].Rone = var; 59         return ; 60     } 61     if( L<=M ) 62         update( rt<<1 , L , var ); 63     else 64         update( rt<<1|1 , L , var ); 65     pushUp( rt ); 66 } 67  68 int query( int rt , int L  ) 69 { 70     int M = ( tree[rt].L + tree[rt].R ) >> 1; 71     if( tree[rt].L == L ) 72         return tree[rt].Lone; 73     if( L<=M ) 74     { 75         if( tree[rt<<1].R - tree[rt<<1].Rone + 1 <= L ) 76         {     77             return query( rt<<1 , L ) + query( rt<<1|1 , M+1 ); 78         } 79         return query( rt<<1 , L  ); 80     } 81     else 82     { 83         return query( rt<<1|1 , L ); 84     } 85 } 86  87 int main() 88 { 89     cin.sync_with_stdio(false); 90     int t , op , a , i , k , ans; 91     char c; 92     int q; 93     cin >> t; 94     for( int Case = 1 ; Case<=t ; Case++ ) 95     { 96         cin >> ss >> tt; 97         init( ); 98         build( 1 , 1 , len ); 99         cin >> q;100         cout << "Case " << Case << ":" << endl;101         while( q-- )102         {103             cin >> op;104             if( op==1 )105             {106                 cin >> a >> i >> c; // 第 a 行的 str[i] 变成 (char)c;107                 if( i>=len )108                     continue;109                 if( a==1 ) //ss110                 {111                     ss[i] = c;112                     if( c==tt[i] )113                         num[i+1] = 1;114                     else115                         num[i+1] = 0;116                 }117                 else118                 {119                     tt[i] = c;120                     if( c==ss[i] )121                         num[i+1] = 1;122                     else123                         num[i+1] = 0;124                 }125                 update( 1 , i+1 , num[i+1] );126             }127             else128             {129                 cin >> k;130                 ans = query( 1 , k+1 );131                 cout << ans << endl;132             }133         }134     }135     return 0;136 }
View Code

 

today:

  r = a ( 1 - sinθ )

 

hdu--4339--线段树