博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
Abandon の 线段树【专辑】（长期更新）
阅读量：5010 次
发布时间：2019-06-12

本文共 46085 字，大约阅读时间需要 153 分钟。

　　先从的《统计与力量》感受了zkw线段树的优美（在此先ym 3分钟……），但是自己还是不能深入理解；后来又看了的线段树，虽然是用递归形式但从优美程度来讲一点儿也不差（zkw的非递归自己在拓展方面很难伸展，功力还不够……），我的线段树主要就是受这两位大牛的风格影响了~~~然后练习呀什么的基本是跟着HH神（NotOnlySuccess）的来的，然后在其他地方看到的很好的题也自己加了进来。

==========================================================================================================================================  

　　对于各类线段树问题来说，

　　结点中主要有两种需要维护的数据，一个是标记，一个是统计。 

　　主要有两种维护操作，一种是标记下放（懒惰标记，用于区间修改），一种是统计汇总（用于区间查询）。

　　可以看出这里我的建树方式采用的是zkw的满二叉树的形式，虽然浪费一些空间（？）但是在点区间对应查找和调试上都非常方便。

==========================================================================================================================================

♥单点更新:最最基础的线段树,只更新叶子节点,然后把信息用PointUpdate(int n, int V) || PointAdd(int n, int V)函数更新上来。

 

　　♠ (线段树入入入门题 || 第一个线段树程序)　

HDU 1166 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;typedef long long ll;const double EPS = 1e-11;void Swap(int &a,int &b){ int t=a;a=b;b=t; }int Max(int a,int b) { return a>b?a:b; }int Min(int a,int b) { return a
                    
                     0;i--) T[i].value=T[2*i].value+T[2*i+1].value;}void PointUpdate(int n, int V) //单点更新{ for (T[n+=M].value=V,n>>=1;n;n>>=1) T[n].value=T[2*n].value+T[2*n+1].value;}void PointAdd(int n, int V) //单点增加，减的话把V变-即可{ for (T[n+=M].value+=V,n>>=1;n;n>>=1) T[n].value=T[2*n].value+T[2*n+1].value;}int Query(int s,int t) //区间、点询问{ int sum=0; for (s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1) { if (~s&1) sum+=T[s^1].value; if (t&1) sum+=T[t^1].value; } return sum;}int main(){ int t; int casenum=1; scanf("%d",&t); while(t--) { printf("Case %d:\n",casenum++); int n; scanf("%d",&n); int a,b; BuildTree(n); char c[6]; //scanf("%*c"); while(scanf("%s",c)) { if (strcmp(c,"End")==0) break; if (strcmp(c,"Query")==0) { scanf("%d%d",&a,&b); printf("%d\n",Query(a,b)); } else if (strcmp(c,"Add")==0) { scanf("%d%d",&a,&b); PointAdd(a,b); } else { scanf("%d%d",&a,&b); PointAdd(a,-b); } } } return 0;}

 

　　♠ ★(好题，逆推思路)

　　问题抽象：求第K小点

　　思路:分析发现， 第i个人对他后面的人的位置都有可能有影响，但对他前面的人的位置一定没有影响。所以，我们可倒着插队。从后向前，先操作第n个人，当操作第i个人时，我们将他插在第pos[i]+1个空处。因为此时区间内的空处，是正着插队时前面奶牛所占的位置。对于求第K点，线段树时跑不过SBT。（嗯~这题可以SBT的......感觉线段树在这儿就是起了一个维护前缀和还有二分搜索的作用......）

POJ 2828 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;typedef long long ll;const double EPS = 1e-11;void Swap(int &a,int &b){ int t=a;a=b;b=t; }int Max(int a,int b) { return a>b?a:b; }int Min(int a,int b) { return a
                    
                     0;i--) T[i].value=T[2*i].value+T[2*i+1].value;}void Insert(int p,int v,int l,int r,int rt) //special operator{ if (l==r) { T[rt].value=0; path[rt]=v; return ; } int mid=(l+r)>>1; if (p<=T[rt<<1].value) Insert(p,v,l,mid,rt<<1); else Insert(p-T[rt<<1].value,v,mid+1,r,rt<<1|1); T[rt].value=T[rt<<1].value+T[rt<<1|1].value; return ;}int main(){ int n; int p[MAX],v[MAX]; while(scanf("%d",&n)!=EOF) { memset(path,0,sizeof(path)); BuildTree(n); for (int i=0;i
                     
                      =0;i--) Insert(p[i]+1,v[i],1,M,1); printf("%d", path[M]); for (int i=1;i

 

　　♠ ★()

　　问题抽象：求特殊区间最大点、最小点。

　　思路:每次左边右边寻找距离当前位置最近的点，则用线段树求[0,now]区间最大数，求[now,l]区间最小的数维护即可。　

HDU 4302 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                 12 #include 
                 
                   13 #include 
                  
                    14 #include 
                   
                     15 #define MID(x,y) ( ( x + y ) >> 1 ) 16 #define FOR(i,s,t) for(int i=s; i
                    
                     >=1;n;n>>=1) 41 PushUp(n); 42 } 43 44 int Qsum(int s,int t,int l,int r,int rt) 45 { 46 if (s<=l && r<=t) 47 { 48 return sum[rt]; 49 } 50 51 int mid=MID(l,r); 52 int ans=0; 53 if (s<=mid) ans+=Qsum(s,t,l,mid,rt<<1); 54 if (mid
                     
                      =s) 67 { 68 return Querymax(s,l,mid,rt<<1); 69 } 70 else return Querymax(s-sum[rt<<1],mid+1,r,rt<<1|1); 71 } 72 73 int Querymin(int s,int l,int r,int rt) 74 { 75 if (l==r) 76 { 77 return l; 78 } 79 80 int mid=MID(l,r); 81 if (sum[rt<<1|1]>=s) 82 { 83 return Querymin(s,mid+1,r,rt<<1|1); 84 } 85 else return Querymin(s-sum[rt<<1|1],l,mid,rt<<1); 86 } 87 88 int main() 89 { 90 //freopen("test.in","r+",stdin); 91 92 int t,caseo=1; 93 scanf("%d",&t); 94 while(t--) 95 { 96 printf("Case %d: ",caseo++); 97 int ans=0; 98 int l,n; 99 scanf("%d%d",&l,&n);100 BuildTree(l);101 int h=0;102 int dir=0;103 for (int i=0;i
                      
                       h-b1)139 {140 ans+=h-b1;141 h=b1;142 dir=-1;143 Update(b1,-1);144 }145 else if (b2-h

 

　　♠ (离线RMQ，更新都不用，轻松1Y，简单题=。=)

POJ 3264 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;typedef long long ll;const double EPS = 1e-11;void Swap(int &a,int &b){ int t=a;a=b;b=t; }int Max(int a,int b) { return a>b?a:b; }int Min(int a,int b) { return a
                    
                     0;i--) { T[i].max=Max(T[2*i].max,T[2*i+1].max); T[i].min=Min(T[2*i].min,T[2*i+1].min); }}int QueryMax(int s,int t){ int maxc=-1; for (s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1) { if (~s&1) maxc=Max(maxc,T[s^1].max); if (t&1) maxc=Max(maxc,T[t^1].max); } return maxc;}int QueryMin(int s,int t){ int minc=INT_MAX; for (s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1) { if (~s&1) minc=Min(minc,T[s^1].min); if (t&1) minc=Min(minc,T[t^1].min); } return minc;}int main(){ int n,q; scanf("%d%d",&n,&q); BuildTree(n); for (int i=0;i

 

　　♠ ★()

　　问题抽象：分组线段树求和。

　　思路:离线(离散化+排序)维护5颗线段树。sum[rt][5]的每棵树表示区间的数以该区间左端为起点mod 5的余数，cnt[rt]表示区间数的数目。一开始不知道怎么动态地维护插入、删除数据的位置的模5的余数，比如一开始插入1、3、5，5是要求的，但要是再插入个2变成1、2、3、5，那么就变成3了。。。这个让我想了好久，后来经过一些提示终于想到了思路:每个叶节点的值都附在sum[rt][0]里，即上面说的，sum[rt][i]表示以该区间左端点为起点mod 5的余数。那么在向上统计汇总时怎么转化呢？

　　答案是：sum[结点][i]=sum[左儿子][i]+sum[右儿子][((i+5)-cnt[左儿子]%5)%5]。

　　什么意思呢？从sum的意义出发，左儿子的区间左端点和父节点是一样的，所以他们的余数等价；然而需要把右儿子的左端点与父节点等价起来。设父区间左端点为a，则右儿子区间左端点即为a+cnt[左儿子]。若右儿子(pos-a)%5==i，则把它放到父区间(pos-a-cnt[])%5== i-cnt[]%5== (保证大于等于0小于5) ((i+5)-cnt[]%5)%5。

　　另外要注意这里离散化的方法~~~lower_bound()函数可以很方便的找到数在原数组中的位置。（或者自己写一个二分也可以。。。）　

HDU 4288 
1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #define MID(x,y) ((x+y)>>1)14 15 using namespace std;16 typedef long long LL;17 18 const int N=100005;19 int M;20 LL sum[N<<2][5];21 int cnt[N<<2];22 23 void BuildTree(int n)24 {25 for (M=1;M<=n+2;M<<=1);26 for (int i=1;i
                  
                   <<2;i++)27 {28 for (int j=0;j<5;j++)29 sum[i][j]=0;30 cnt[i]=0;31 }32 }33 34 void PushUp(int rt)35 {36 cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1];37 for (int i=0;i<5;i++)38 sum[rt][i]=sum[rt<<1][i]+sum[rt<<1|1][((i+5)-cnt[rt<<1]%5)%5];39 }40 41 void Update(int s,int num,int v,int l,int r,int rt)42 {43 if (l==s && r==s)44 {45 sum[rt][0]+=v*num;46 cnt[rt]+=num;47 return;48 }49 50 int mid=MID(l,r);51 if (s<=mid) Update(s,num,v,l,mid,rt<<1);52 else Update(s,num,v,mid+1,r,rt<<1|1);53 PushUp(rt);54 }55 56 char str[100005][5];57 int pri[100005];58 int a[100005];59 60 int main()61 {62 //freopen("test.in","r+",stdin);63 int n;64 while(scanf("%d",&n)!=EOF)65 {66 int tot=0;67 for (int i=0;i

 

　　♠ ★()

　　问题抽象：询问区间内比一个数的权值小的数的个数

　　思路：将所有的询问离线读入之后，按H从小到大排序。对于所有的节点也按从小到大排序，然后根据查询的H，将比H小的点加入到线段树，然后就是一个区间和。

　　另一个思路：二分+区间第k大（划分树、函数式线段树……）

HDU 4417 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #define MID(x,y) ((x+y)>>1) 13 14 using namespace std; 15 16 const int N=100500; 17 struct Co 18 { 19 int l,r; 20 int h; 21 int p; 22 }co[N]; 23 24 struct Po 25 { 26 int i; 27 int h; 28 friend bool operator < (const Po &a,const Po &b) 29 { 30 return a.h>b.h; 31 } 32 }; 33 priority_queue 
                 
                   > Q; 34 Po po[N]; 35 int ans[N]; 36 37 bool cmp(Co a,Co b) 38 { 39 return a.h
                  
                   >=1;n;n>>=1) 57 PushUp(n); 58 } 59 int query(int s,int t,int l,int r,int rt) 60 { 61 if (s<=l && r<=t) 62 { 63 return sum[rt]; 64 } 65 66 int mid=MID(l,r); 67 int res=0; 68 if (s<=mid) res+=query(s,t,l,mid,rt<<1); 69 if (mid

 

　　♠ ★()

　　问题抽象：询问区间内比一个数的first权值大的数中second权值最大的数

　　思路：先一遍dfs将树形结构转为线性结构，转化后的每个点对应一个区间，区间内是它所有的子孙。然后问题就转化成了求区间内比一个数的权值大的数中权值最大的数。和上面那题很像了。将所有询问离线读入，按能力值从大到小排序。对于节点也按从大到小排序，然后根据查询点的能力值，将比它能力值大的点都插进线段树中，这样保证了线段树中存的都是满足条件的数（能力比上司高），再在对应区间内找个忠诚值最高的就好了（线段树中维护个max值什么的...）。

　　悲剧的是我在dfs爆栈了=.=。。。其实我觉得这个栈溢出的挺正常，毕竟50000个点压进栈什么的...=.=，可别人的为什么不会呀T_T，姿势也差不多呢呀，HDU 4358那道题为什么没爆呀=.=。。。算了，先放着吧，有时间了手动模拟栈再重新做一遍。。。

 

♥区间更新:(通常这对初学者来说是一道坎)需要用到延迟标记(懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候。（这个阶段zkw线段树的精髓吾尚不能参透T_T......所以就结合用懒惰标记了=。=......）

 

注意 
由于是对每个区间的值进行修改，如果我们每次修改都修改到叶子节点，那么修改复杂度就降到了O(n)，必然导致TLE，所以要用懒惰标记。｛ 注意这里默认的总区间是[1..M]不是HH大牛的[1..n]，用错了区间和数组下标会对不上（因为zkw式建树和HH大牛的建树方式不同，zkw式在BuildTree()时建的就是[1,M]的满二叉树，这样建树的好处是下标与区间对应的很工整（详见《统计的力量》），查找会很方便。而HH牛的线段树开的是[1,n]的树）。。。而且要注意初始化时是从M赋值还是M+1，如果从M开始赋值（第0个叶节点开始表示区间1），则总区间为[1..M]；如果从M+1开始赋值（用第1个叶节点开始表示区间1->前面还有第0个叶节点），则总区间为[0..M-1]。为了方便且易查错，我的程序就统一从M开始赋值，总区间定为[1,M] ｝

 

　　懒惰标记就是:如果当前的区间被要更新的区间所覆盖，直接就改变当前结点的信息，不用再往下了，所以，每次在更新的时候，只更新一层，把当前结点的信息往下传递一层，以供下一步使用，如果下一步完成了更新，更新也就结束了，没有完成，继续往下传递一层。。。。

 

　　♠ (区域修改->懒惰标记 入门题)

POJ 3468 
1 POJ 3468  2   3 #include 
      
         4 #include 
       
          5 #include 
        
           6 #include 
         
            7 #include 
          
             8 #include 
           
             9 #include 
            
              10 #include 
             
               11 #include 
              
                12 #include 
               
                 13 #include 
                 14 #include 
                 
                   15 #include 
                  
                    16 #include 
                   
                     17 18 using namespace std; 19 20 typedef long long LL; 21 const double EPS = 1e-11; 22 23 //zkw线段树模板————区间更新 24 25 const int N=100005; //结点个数 26 27 int M; 28 __int64 sum[N<<2]; //M*2，特殊情况M会接近2*N。比如N=1023[1,1023]，则M=2048---zkw《统计的力量》 29 __int64 add[N<<2]; 30 31 void PushUp(int rt) //统计汇总，rt为当前节点 32 { 33 sum[rt] = sum[rt<<1] + sum[rt<<1|1]; //如果是区间最值则 sum[n]=max(sum[n*2],sum[n*2+1]) 34 } 35 36 void BuildTree(int n) 37 { 38 for (M=1;M<=n+2;M<<=1); //求出M值（查询区间[1，M]） 39 for (int i=1;i<(N<<2);i++) 40 { 41 sum[i]=0; 42 add[i]=0; 43 } 44 for (int i=M;i
                    
                     0;i--) 47 PushUp(i); 48 } 49 50 void PushDown(int rt,int l) //标记下放，rt为当前节点，l为修改区间长度 51 { 52 if (add[rt]) 53 { 54 add[rt<<1]+=add[rt]; 55 add[rt<<1|1]+=add[rt]; 56 sum[rt<<1]+=add[rt]*(l-(l>>1)); 57 sum[rt<<1|1]+=add[rt]*(l>>1); 58 add[rt]=0; 59 } 60 } 61 62 void Update(int s,int t,int v,int l,int r,int rt) 63 { 64 if (s<=l && r<=t) 65 { 66 add[rt]+=v; 67 sum[rt]+=v*(r-l+1); 68 return ; 69 } 70 PushDown(rt,r-l+1); 71 int m=(l+r)>>1; 72 if (s<=m) Update(s,t,v,l,m,rt<<1); 73 if (m
                     
                      >1; 84 if (s<=m) ans+=Query(s,t,l,m,rt<<1); 85 if (m

 

　　♠ ★() 

　　思路:如果没有防守间隔的限制，那么就是一道裸的线段树区间增减、单点查询问题。防守间隔的限制貌似阻碍了我们直接对区间修改，因为区间中不同点的防守状态不尽相同，就要个个针对，如果这样貌似的话就又退化成了N次单点更新---显然不可取。

　　一个重要的思路就是分而治之---把攻击和防守分开考虑。截至当前时间，一个点被成功攻击的次数 = 总攻击数 - 这段时间这个点防御的次数。（具体怎么求防守次数，看了代码就会很好理解的~~~）（因为模板的初始化sum add的范围(1, 2<<N)没弄对WA一次T_T……又返回去把前面的模板修正了下……）　

HDU 4031 
1 #include
      
         2 #include
       
          3 #define lson l,m,rt<<1  4 #define rson m+1,r,rt<<1|1  5 const int N = 20001;  6 int M;  7 int sum[N<<2];  8 int add[N<<2];  9  10 struct pp{ 11     int l,r; 12 }att[N]; 13  14 int defen[N]; 15  16 void PushUp(int rt)             //统计汇总，rt为当前节点 17 { 18     sum[rt] = sum[rt<<1] + sum[rt<<1|1];    //如果是区间最值则 sum[n]=max(sum[n*2],sum[n*2+1]) 19 } 20  21 void PushDown(int rt,int l)        //标记下放，rt为当前节点，l为修改区间长度 22 { 23     if (add[rt]) 24     { 25         add[rt<<1]+=add[rt]; 26         add[rt<<1|1]+=add[rt]; 27         sum[rt<<1]+=add[rt]*(l-(l>>1)); 28         sum[rt<<1|1]+=add[rt]*(l>>1); 29         add[rt]=0; 30     } 31 } 32  33 void BuildTree(int n) 34 { 35     for (M=1;M<=n+2;M<<=1);            //求出M值（查询区间[1，M]） 36     for (int i=1;i
        
         0;i--) 42         PushUp(i); 43 } 44  45  46 void Update(int s,int t,int v,int l,int r,int rt) 47 { 48     if (s<=l && r<=t) 49     { 50         add[rt]+=v; 51         sum[rt]+=v*(r-l+1); 52         return ; 53     } 54     PushDown(rt,r-l+1); 55     int m=(l+r)>>1; 56     if (s<=m)   Update(s,t,v,l,m,rt<<1); 57     if (m
         
          >1; 68     if (s<=m)   ans+=Query(s,t,l,m,rt<<1); 69     if (m
          
           =att[i].l&&a<=att[i].r){ 97                         defen[a]++; 98                         i+=t0-1; 99                     }100                 }101                 printf("%d\n",Query(a,a,1,M,1)-defen[a]);102 103 104             }105         }106     }107     return 0;108 }

 

　　♠ ★()

　　思路:这道题的难点在于处理平方根时区间不好处理。一开始把思路集中在和的平方根和平方根的和的关系上，果然还是思维不够宽阔呐~这道题如果能想到一个I64整数也最多开平方8次就成1的话就简单了。在区间上加一个域bol[]判断该区间的数是不是都是1了，如果是则不用修改了。这样下来没个点最多被修改8次，不会超时。

HDU 4027 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #define MID(x,y) ( ( x + y ) >> 1 ) 14 #define FOR(i,s,t) for(int i=s; i
                  
                   0;i--) 51 PushUp(i); 52 } 53 54 55 void Update(int s,int t,int l,int r,int rt) 56 { 57 if (s<=l && r<=t) 58 { 59 if (bol[rt]==1) 60 return ; 61 else if (l==r) 62 { 63 sum[rt]=(__int64)sqrt(double(sum[rt])); 64 if (sum[rt]==1) 65 bol[rt]=1; 66 return ; 67 } 68 } 69 70 int m=MID(l,r); 71 if (s<=m) Update(s,t,l,m,rt<<1); 72 if (m
                   
                    b) a^=b, b^=a, a^=b;110 Update(a,b,1,M,1);111 }112 else113 {114 int a,b;115 116 scanf("%d%d",&a,&b);117 if (a>b) a^=b, b^=a, a^=b;118 printf("%I64d\n",Query(a,b,1,M,1));119 }120 }121 122 printf("\n");123 }124 125 126 return 0;127 }

　　

　　♠ (坐标离散化->数组hash)

　　问题抽象：线段插入问题。（通常需要把坐标离散化成“线段”）

 

思路 
这题的坐标范围有点儿大(1-10000000)，普通线段树肯定会超时+超内存，所以就需要离散化：　　离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012] 我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我只需要1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了　　所以离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多　　而这题的难点在于每个数字其实表示的是一个单位长度(并非一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)　　给出下面两个简单的例子应该能体现普通离散化的缺陷:　　例子一:1-10 1-4 5-10　　例子二:1-10 1-4 6-10　　普通离散化后都变成了[1,4][1,2][3,4]　　线段2覆盖了[1,2],线段3覆盖了[3,4],那么线段1是否被完全覆盖掉了呢?　　例子一是完全被覆盖掉了,而例子二没有被覆盖　　为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]　　如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.　　PS:这题我写的程序和一个AC程序对拍了N次没错，但交到POJ就是WA。。。哎，算了，留待以后写吧。。。

 

 

　　♠ ()(坐标离散化->map hash)　

HDU 4325 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #define MID(x,y) ((x+y)>>1) 13 14 using namespace std; 15 16 const int MAXN = 200100; 17 int M; 18 int sum[MAXN<<2],add[MAXN<<2]; 19 20 void build(int n) 21 { 22 for (M = 1; M <= n+2; M <<= 1); 23 for (int i = 1; i < MAXN << 2; i ++) 24 sum[i] = 0, add[i] = 0; 25 } 26 27 void PushDown(int rt,int l) 28 { 29 if (add[rt]) 30 { 31 add[rt<<1] += add[rt]; 32 add[rt<<1|1] += add[rt]; 33 sum[rt<<1] += add[rt] * (l - (l >> 1)); 34 sum[rt<<1|1] += add[rt] * (l >> 1); 35 add[rt] = 0; 36 } 37 } 38 39 void Update(int s,int t,int v,int l,int r,int rt) 40 { 41 if (s <= l && r <= t) 42 { 43 add[rt] += v; 44 sum[rt] += v * (r - l + 1); 45 return ; 46 } 47 PushDown(rt, r-l+1); 48 int mid = MID(l,r); 49 if (s <= mid) Update(s,t,v,l,mid,rt<<1); 50 if (mid < t) Update(s,t,v,mid+1,r,rt<<1|1); 51 } 52 53 int query(int p,int l,int r,int rt) 54 { 55 if (l == p && r == p) 56 { 57 return sum[rt]; 58 } 59 60 PushDown(rt,r-l+1); 61 int mid = MID(l,r); 62 int res = 0; 63 if (p <= mid) res += query(p,l,mid,rt<<1); 64 else res += query(p,mid+1,r,rt<<1|1); 65 return res; 66 } 67 68 struct seg 69 { 70 int x,y; 71 }p[MAXN]; 72 73 int ask[MAXN]; 74 int b[MAXN]; 75 map 
                 
                   mm; 76 77 int main() 78 { 79 int t,caseo=1; 80 scanf("%d",&t); 81 while(t--) 82 { 83 int tot=0; 84 memset(p,0,sizeof(p)); 85 mm.clear(); 86 printf("Case #%d:\n",caseo ++); 87 int n,m; 88 scanf("%d%d",&n,&m); 89 for (int i = 0; i < n; i ++) 90 { 91 scanf("%d%d",&p[i].x,&p[i].y); 92 b[tot ++] = p[i].x; 93 b[tot ++] = p[i].y; 94 } 95 for (int i = 0; i < m; i ++) 96 { 97 scanf("%d",&ask[i]); 98 b[tot++] = ask[i]; 99 }100 sort(b, b + tot);101 int tt=1;102 for (int i = 0; i < tot; i ++)103 if (mm.find(b[i]) == mm.end())104 mm[b[i]] = tt ++;105 build(tt);106 for (int i = 0; i < n; i ++)107 {108 int a = mm[p[i].x];109 int b = mm[p[i].y];110 Update(a, b, 1, 1, M, 1);111 }112 for (int i = 0; i < m; i ++)113 {114 int a = mm[ask[i]];115 printf("%d\n",query(a, 1, M, 1));116 }117 }118 return 0;119 }

　　

　　♠ ★()(分组线段树)

　　做网络赛的时候没想到（经验太少了T T……），比完赛请教了一个大牛才学会这种处理方法。

　　思路: 比较容易往线段树上想的。但是由于更新的是一些离散的点，比较麻烦。可以考虑这些点的共性，总是隔几个，更新一个，而且注意这个条件“(i-a)%k==0”可以转化为“i%k == a%k ==mod ”，那么我们就可以把区间内的数关于k的余数分组。这样每次更新的都是其中的一组，而且是连续的。由于 K比较小，这是本题的突破口，那么关于k的余数情况，最多只有55种。即如果k=1，则分为1组，k=2分为2组……（如果直接开10*10的数组会MLE = =……今年卡内存卡的那叫个……）最后查询也一样，枚举点所在的所有分组上的和都加起来就行了。

HDU 4267 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #define MID(x,y) ( ( x + y ) >> 1 ) 14 15 using namespace std; 16 17 #define N 50002 18 19 int sum[N<<2],add[N<<2][55]; 20 int ha[11][11]; 21 int op[N]; 22 23 void BuildTree(int rt,int l,int r) 24 { 25 sum[rt]=0; 26 memset(add[rt],0,sizeof(add[rt])); 27 if (l==r) return ; 28 29 int mid=MID(l,r); 30 BuildTree(rt<<1,l,mid); 31 BuildTree(rt<<1|1,mid+1,r); 32 } 33 34 void PushDown(int rt) 35 { 36 if (sum[rt]) 37 { 38 sum[rt<<1]+=sum[rt]; 39 sum[rt<<1|1]+=sum[rt]; 40 sum[rt]=0; 41 for (int i=0;i<55;i++) 42 { 43 add[rt<<1][i]+=add[rt][i]; 44 add[rt<<1|1][i]+=add[rt][i]; 45 add[rt][i]=0; 46 } 47 } 48 } 49 50 void Update(int s,int t,int v,int l,int r,int rt,int i,int j) 51 { 52 if (s<=l && r<=t) 53 { 54 sum[rt]+=v; 55 add[rt][ha[i][j]]+=v; 56 return ; 57 } 58 59 PushDown(rt); 60 int mid=MID(l,r); 61 if (s<=mid) Update(s,t,v,l,mid,rt<<1,i,j); 62 if (mid

 

　　♠ ★()(分组线段树)

　　HH神出的一道线段树神题~

　　思路：题意很简单,成段更新,成段询问,但是更新却和一般的线段树大不一样,每个点虽然接收到相同的信息,但是由于本身不同,最终得到的值也是不同的.用一般的延迟操作就搞不定了.

　　突破点在K,范围很小,只有10,可以考虑每次有人升级的时候,就递归的找下去,将这个人进行升级操作.由于找到某个人只需要logn的复杂度,每个人最多升k次,所以n个人的复杂度是O(nklogn)。用了两个辅助数组add[maxn]和MAX[maxk][maxn],add用于记录延迟标记,MAX[k]表示该区间等级为k的最大经验值.初始化add,MAX[1]为0,其他为-1,表示无人在这个等级.当MAX[k]的值大于等于Needk时,就对这个区间进行升级操作,和线段树操作一样递归的将这个区间能升级的人全部升级.

　　单次操作可能会是nlogn(每个人都升级),但是平均下来还是只有nklogn.

HDU 3954 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
                11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 #define MID(x,y) ( ( x + y ) >> 1 ) 15 16 using namespace std; 17 18 typedef long long LL; 19 20 const int N=10005; 21 int M; 22 int maxn[N<<2][11],add[N<<2]; 23 int need[11]; 24 int n,k,QW; 25 26 void PushUp(int rt) 27 { 28 for (int i=1;i<=k;i++) 29 maxn[rt][i]=max(maxn[rt<<1][i],maxn[rt<<1|1][i]); 30 } 31 32 void PushDown(int rt) 33 { 34 if (add[rt]) 35 { 36 add[rt<<1]+=add[rt]; 37 add[rt<<1|1]+=add[rt]; 38 for (int i=1;i<=k;i++) 39 { 40 if (maxn[rt<<1][i]!=-1) 41 maxn[rt<<1][i]+=i*add[rt]; 42 if (maxn[rt<<1|1][i]!=-1) 43 maxn[rt<<1|1][i]+=i*add[rt]; 44 } 45 add[rt]=0; 46 } 47 } 48 49 void BuildTree(int n) 50 { 51 for (M=1;M<=n+2;M<<=1); 52 53 for (int i=1;i
                   
                    <<2;i++) 54 { 55 for (int j=0;j<11;j++) 56 maxn[i][j]=-1; 57 add[i]=0; 58 maxn[i][1]=0; 59 } 60 } 61 62 void LevelUp(int i,int s,int t,int l,int r,int rt) 63 { 64 if (s<=l && r<=t) 65 { 66 if (l==r) 67 { 68 while(i
                    
                     =1;i--) 92 { 93 if (maxn[rt][i]!=-1) 94 { 95 maxn[rt][i]+=i*ei; 96 if (i!=k && maxn[rt][i]>=need[i+1]) 97 LevelUp(i,s,t,l,r,rt); 98 } 99 }100 101 return ;102 103 }104 105 PushDown(rt);106 int mid=MID(l,r);107 if (s<=mid) Update(s,t,ei,l,mid,rt<<1);108 if (mid
                     
                      >c;147 if (c=='W')148 {149 int a,b,ei;150 scanf("%d%d%d",&a,&b,&ei);151 Update(a,b,ei,1,M,1);152 }153 else154 {155 int a,b;156 scanf("%d%d",&a,&b);157 printf("%d\n",Query(a,b,1,M,1));158 }159 }160 printf("\n");161 }162 return 0;163 }

 

　　♠ ★★()

　　问题抽象：区间内恰好出现K次的数的个数。

　　思路： （内容有点儿多，单独放一处了）

 

　　♠ ★(区间异或&&分组线段树)

　　题目大意：序列a有n个数。实现两个操作：①求[l,r]区间和　　②对某个区间[l,r]所有数异或一个数x。

　　思路：比较容易想到是用线段树，因为每个数都小于10^6，所以把每一位拆成20位储存，这样就用20颗线段树。那么问题就转化为区间01异或问题：0异或任何数不变，不用修改，1异或一个数x结果是1-x。。（详细理解还是看代码吧。。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #define MID(l,r) (l + r)/2using namespace std;const int N = 100010;long long sum[22][N<<2],cnt[N<<2],ans[22];void pushup(int rt){ for (int i = 0; i < 20; i ++){ sum[i][rt] = sum[i][rt<<1] + sum[i][rt<<1|1]; }}void pushdown(int rt,int w){ if (cnt[rt]){ cnt[rt<<1] ^= cnt[rt]; cnt[rt<<1|1] ^= cnt[rt]; for (int i = 0; i < 20; i ++){ if (cnt[rt] >> i & 1){ sum[i][rt<<1] = w - (w >> 1) - sum[i][rt<<1]; sum[i][rt<<1|1] = (w >> 1) - sum[i][rt<<1|1]; } } cnt[rt] = 0; }}void build(int l,int r,int rt){ if (l == r){ long long x; cin>>x; for (int i = 0; i < 20; i ++){ sum[i][rt] = x >> i & 1; } return ; } int mid = MID(l,r); build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); pushup(rt); return ;}void update(int s,int t,int c,int l,int r,int rt){ if (s <= l && r <= t){ cnt[rt] ^= c; for (int i = 0; i < 20; i ++){ if (c >> i & 1){ sum[i][rt] = r - l + 1 - sum[i][rt]; } } return ; } pushdown(rt,r-l+1); int mid = MID(l,r); if (s <= mid) update(s,t,c,l,mid,rt<<1); if (mid < t) update(s,t,c,mid+1,r,rt<<1|1); pushup(rt);}void query(int s,int t,int l,int r,int rt){ if (s <= l && r <= t){ for (int i = 0; i < 20; i ++){ ans[i] += sum[i][rt]; } return ; } pushdown(rt,r-l+1); int mid = MID(l,r); if (s <= mid) query(s,t,l,mid,rt<<1); if (mid < t) query(s,t,mid+1,r,rt<<1|1);}long long getquery(int s,int t,int l,int r){ memset(ans,0,sizeof(ans)); query(s,t,l,r,1); long long res = 0; for (int i = 0; i < 20; i ++){ res += (1LL << i) * ans[i]; } return res;}int main(){ int n; scanf("%d",&n); memset(sum,0,sizeof(sum)); memset(cnt,0,sizeof(cnt)); build(1,n,1); int q; scanf("%d",&q); for (int i = 0; i < q; i ++){ int w; scanf("%d",&w); if (w == 1){ int a,b; cin>>a>>b; cout<
             
              <
              
               >a>>b>>c; update(a,b,c,1,n,1); } } return 0;}

 

♥区间合并:这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并，所以一般情况下除了设置本区间最长连续mmax外，还需要设置从区间左端开始最长连续lmax和从区间右端开始最长连续rmax，以便于和左右两边区间合并。

　　

　　♠ （区间合并入门）

　　题目大意：区间内最长连续房间数。

　　问题出来了，对于二叉树，或许某子树根的左孩子的右边跟右孩子的左边连续着呢，怎么办？ 

　　于是，我们开出三个数组 lsum[] rsum[] 和 sum[]。对于区间 [L, R]，lsum[rt]表示以 L为开头的最长连续房间数，rsum[rt]表示以R为结尾的最长连续房间数，sum[]表示[L,R]内的最长连续房间。

　　继续分析：当 lsum[rt<<1]等于左孩子区间总长度时，lsum[rt<<1]和lsum[rt<<1|1] (即左孩子的lsum和右孩子的lsum)是相连的；

　　同理得， 当 rsum[rt<<1|1]等于右孩子总长度时，rsum[rt<<1|1]和rsum[rt<<1]（即右孩子的rsum和左孩子的rsum）是相连的。

　　而对于一个 sum[rt]= max{ rsum[rt<<1]+lsum[rt<<1|1], sum[rt<<1], sum[rt<<1|1 }。

POJ 3667 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #define MID(x,y) ((x+y)>>1) 13 14 using namespace std; 15 16 typedef long long LL; 17 18 const int N=50005; 19 int mmax[N<<2],lmax[N<<2],rmax[N<<2],cov[N<<2]; 20 21 void BuildTree(int l,int r,int rt) 22 { 23 mmax[rt]=lmax[rt]=rmax[rt]=r-l+1; 24 cov[rt]=-1; 25 if (l==r) return; 26 int mid=MID(l,r); 27 BuildTree(l,mid,rt<<1); 28 BuildTree(mid+1,r,rt<<1|1); 29 } 30 31 void PushUp(int rt,int w) 32 { 33 lmax[rt]=lmax[rt<<1]; 34 rmax[rt]=rmax[rt<<1|1]; 35 if (lmax[rt]==w-(w>>1)) lmax[rt]+=lmax[rt<<1|1]; 36 if (rmax[rt]==(w>>1)) rmax[rt]+=rmax[rt<<1]; 37 mmax[rt]=max(rmax[rt<<1]+lmax[rt<<1|1],max(mmax[rt<<1],mmax[rt<<1|1])); 38 } 39 40 void PushDown(int rt,int w) 41 { 42 if (cov[rt]!=-1) //cov的作用只是向下传递标记时区别是清空还是住满该区间。 43 { //cov在区间修改时决定，而那时的Update区间意味着要么住满要么清空 44 cov[rt<<1]=cov[rt<<1|1]=cov[rt]; 45 mmax[rt<<1]=lmax[rt<<1]=rmax[rt<<1]=cov[rt]?0:w-(w>>1); //cov=1，则mmax,lmax,rmax=0，表示住满 46 mmax[rt<<1|1]=lmax[rt<<1|1]=rmax[rt<<1|1]=cov[rt]?0:(w>>1); //cov=0，则mmax,lmax,rmax=区间长度，表示清空 47 cov[rt]=-1; //一定要注意下放标记后要重置！ 48 } 49 } 50 51 void Update(int s,int t,int c,int l,int r,int rt) //c=1表示要住进，c=0表示要清空 52 { 53 if (s<=l && r<=t) 54 { 55 cov[rt]=c; 56 mmax[rt]=lmax[rt]=rmax[rt]=c?0:(r-l)+1; 57 return ; 58 } 59 60 PushDown(rt,r-l+1); 61 int mid=MID(l,r); 62 if (s<=mid) Update(s,t,c,l,mid,rt<<1); 63 if (mid
                 
                  =L) return Query(L,l,mid,rt<<1); //按从左向右的顺序选 74 else if (rmax[rt<<1]+lmax[rt<<1|1]>=L) return mid-rmax[rt<<1]+1; 75 else return Query(L,mid+1,r,rt<<1|1); 76 } 77 78 int main() 79 { 80 //freopen("test.in","r+",stdin); 81 int n,m; 82 scanf("%d%d",&n,&m); 83 BuildTree(1,n,1); 84 for (int i=0;i

 

　　♠ ()

　　问题抽象：最长连续公共子串

　　一开始想了个二分的线段树方法，不过nlog2n超时了。。。

62 Abandon.burning 2000MS 10444K 2333B C++ 2012-10-01 08:42:19
HDU 4339 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #define MID(x,y) ((x+y)>>1) 13 14 using namespace std; 15 const int maxn = 1000100; 16 int lmax[maxn<<2]; 17 char s[2][maxn]; 18 19 void pushUp(int rt,int w) 20 { 21 lmax[rt] = lmax[rt<<1]; 22 if (lmax[rt<<1] == w - (w >> 1)) 23 lmax[rt] += lmax[rt<<1|1]; 24 } 25 void build(int l,int r,int rt) 26 { 27 if (l == r) 28 { 29 if (s[0][l-1] == s[1][l-1]) 30 lmax[rt] = 1; 31 else lmax[rt] = 0; 32 return ; 33 } 34 int mid = MID(l,r); 35 build(l,mid,rt<<1); 36 build(mid+1,r,rt<<1|1); 37 pushUp(rt,r-l+1); 38 } 39 void Update(int p,int a,char c,int l,int r,int rt) 40 { 41 if (p == l && p == r) 42 { 43 s[a-1][p-1] = c; 44 if (s[0][p-1] == s[1][p-1]) 45 lmax[rt] = 1; 46 else lmax[rt] = 0; 47 return ; 48 } 49 50 int mid = MID(l,r); 51 if (p <= mid) Update(p,a,c,l,mid,rt<<1); 52 else Update(p,a,c,mid+1,r,rt<<1|1); 53 pushUp(rt,r-l+1); 54 } 55 56 int query(int s,int t,int l,int r,int rt) 57 { 58 if (s <= l && r <= t) 59 { 60 return lmax[rt]; 61 } 62 63 int mid = MID(l,r); 64 int res = 0; 65 if (s <= mid) 66 { 67 res += query(s,t,l,mid,rt<<1); 68 if (res != mid - s + 1) return res; 69 } 70 if (mid < t) res += query(s,t,mid+1,r,rt<<1|1); 71 return res; 72 } 73 74 int main() 75 { 76 //freopen("test.in","r+",stdin); 77 78 int t, caseo = 1; 79 scanf("%d", &t); 80 while(t--) 81 { 82 printf("Case %d:\n", caseo ++); 83 scanf("%s",s[0]); 84 scanf("%s",s[1]); 85 int n = max(strlen(s[0]), strlen(s[1])); 86 build(1,n,1); 87 int Q; 88 scanf("%d",&Q); 89 while(Q--) 90 { 91 int d; 92 scanf("%d",&d); 93 if (d == 1) 94 { 95 int a,p; 96 char c; 97 scanf("%d%d",&a,&p); 98 cin>>c; 99 p ++;100 Update(p,a,c,1,n,1);101 }102 else103 {104 int p;105 scanf("%d",&p);106 p ++;107 printf("%d\n",query(p,n,1,n,1));108 }109 }110 }111 return 0;112 }

 

　　♠ ★★() (线段树值得研究的一道好题)

　　区间合并->二次合并(pushup)->更新时要合并左右子区间,询问时要合并左右询问子区间（这是不一样的，比如在[1,8]中询问[1,6]，那么左右子区间分别是[1,4],[5,8]，而左右询问子区间是[1,4],[5,6]）。

　　预备知识：一个数的数字根就是这个数mod 9的余数 (余数为0则取9，当然如果这个数本身是0那就是0了……)

　　思路：因为题目中所查询的区间，是所有的子区间的结果的并。所以区间合并就很必要了。

　　每个结点，记录这个区间的和的数根， 记录本区间内从左端点为端点往右的连续区间出现的数根，从右端点为端点往左的连续区间出现的数根，以及整个区间能出现的数根。然后合并什么的。。。

　　但显然还没有结束，不然我也不会把他视作好题了。。。这道题用线段树会卡时限！需要各种优化------主要是算数字根的打表优化。

　　做了一天吧T_T。。。上午想好了思路，然后一下午+晚上完成了一个加上打表、输入输出优化还是TLE的代码。。。T_T。。。然后就捉鸡了。。。

HDU 4351(TLE sb代码) 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #define MID(x,y) ((x+y)>>1) 13 14 using namespace std; 15 const int maxn = 100100; 16 int mmax[maxn<<2],lsum[maxn<<2][10],rsum[maxn<<2][10],ssum[maxn<<2][10]; 17 int mans[maxn<<2],ans[maxn<<2][10],lans[maxn<<2][10],rans[maxn<<2][10]; 18 int mul[10][10]; //合并i,j打表优化 19 20 void initial() 21 { 22 for (int i = 0; i < 10; i ++) 23 for (int j = 0; j < 10; j ++) 24 { 25 int k = i + j; 26 while (k > 9) 27 k -= 9; 28 mul[i][j] = k; 29 } 30 } 31 //外挂优化。。。 32 char CHAR() 33 { 34 char res; 35 while (res = getchar(), !isalpha(res)); 36 return res; 37 } 38 inline void scanf_(int &num) 39 { 40 char in; 41 bool neg = false; 42 while(((in = getchar()) > '9' || in <'0') && in != '-') ; 43 if(in == '-') 44 { 45 neg = true; 46 while((in = getchar()) >'9' || in < '0'); 47 } 48 num = in - '0'; 49 while(in = getchar(),in >= '0' && in <= '9') 50 num *= 10, num += in - '0'; 51 if(neg) 52 num = 0 - num; 53 } 54 inline void printf_(int num) 55 { 56 if(num < 0) 57 { 58 putchar('-'); 59 num =- num; 60 } 61 int ans[10],top = 0; 62 while(num != 0) 63 { 64 ans[top ++] = num % 10; 65 num /= 10; 66 } 67 if(top == 0) 68 putchar('0'); 69 for(int i = top - 1; i >= 0; i --) 70 { 71 char ch = ans[i] + '0'; 72 putchar(ch); 73 } 74 //putchar('\n'); 75 } 76 77 //线段树部分 78 inline void pushUp(int rt) 79 { 80 for (int i = 0; i < 10; i ++) 81 { 82 lsum[rt][i] = lsum[rt<<1][i]; 83 rsum[rt][i] = rsum[rt<<1|1][i]; 84 ssum[rt][i] = (ssum[rt<<1][i] == 1)?1:ssum[rt<<1|1][i]; 85 } 86 //修改区间和数字根 87 int k = mul[mmax[rt<<1]][mmax[rt<<1|1]]; 88 mmax[rt] = k, ssum[rt][k] = 1; 89 90 for (int i = 0; i < 10; i ++) 91 { 92 //右前缀+区间和扩展前缀数字根和子区间数字根 93 if (lsum[rt<<1|1][i]) 94 { 95 int k = mul[mmax[rt<<1]][i]; 96 lsum[rt][k] = 1, ssum[rt][k] = 1; 97 } 98 //左后缀+区间和扩展后缀数字根和子区间数字根 99 if (rsum[rt<<1][i])100 {101 int k = mul[mmax[rt<<1|1]][i];102 rsum[rt][k] = 1, ssum[rt][k] = 1;103 104 //左后缀+右前缀扩展子区间数字根105 for (int j = 0; j < 10; j ++)106 if (lsum[rt<<1|1][j])107 {108 int k = mul[i][j];109 ssum[rt][k] = 1;110 }111 }112 }113 }114 115 inline void pushUpAns(int rt)116 {117 //查询时也要合并左右区间...118 for (int i = 0; i < 10; i ++)119 {120 lans[rt][i] = lans[rt<<1][i];121 rans[rt][i] = rans[rt<<1|1][i];122 ans[rt][i] = (ans[rt<<1][i] == 1)?1:ans[rt<<1|1][i];123 }124 for (int i = 0; i < 10; i ++)125 {126 if (lans[rt<<1|1][i])127 {128 int k = mul[mans[rt<<1]][i];129 lans[rt][k] = 1, ans[rt][k] = 1;130 }131 if (rans[rt<<1][i])132 {133 int k = mul[mans[rt<<1|1]][i];134 rans[rt][k] = 1, ans[rt][k] = 1;135 }136 if (rans[rt<<1][i])137 for (int j = 0; j < 10; j ++)138 if (lans[rt<<1|1][j])139 {140 int k = mul[i][j];141 ans[rt][k] = 1;142 }143 }144 }145 146 void build(int l,int r,int rt)147 {148 if (l == r)149 {150 mmax[rt] = 0;151 for (int i = 0; i < 10; i ++)152 {153 lsum[rt][i] = 0;154 rsum[rt][i] = 0;155 ssum[rt][i] = 0;156 }157 int a;158 scanf_(a);159 if (!a) { mmax[rt] = 0; lsum[rt][0] = 1; rsum[rt][0] = 1; ssum[rt][0] = 1; }160 else161 {162 a = a % 9;163 if (!a) { mmax[rt] = 9; lsum[rt][9] = 1; rsum[rt][9] = 1; ssum[rt][9] = 1; }164 else { mmax[rt] = a; lsum[rt][a] = 1; rsum[rt][a] = 1; ssum[rt][a] = 1; }165 }166 return ;167 }168 int mid = MID(l,r);169 build(l, mid, rt<<1);170 build(mid+1, r, rt<<1|1);171 pushUp(rt);172 }173 174 int query(int s,int t,int l,int r,int rt)175 {176 if (s <= l && r <= t)177 {178 for (int i = 9; i >= 0; i --)179 {180 if (ssum[rt][i])181 ans[rt][i] = 1;182 if (lsum[rt][i])183 lans[rt][i] = 1;184 if (rsum[rt][i])185 rans[rt][i] = 1;186 }187 mans[rt] = mmax[rt];188 while (mans[rt] > 9) mans[rt] -= 9;189 return mmax[rt];190 }191 int res = 0;192 int mid = MID(l,r);193 if (s <= mid) res += query(s,t,l,mid,rt<<1);194 if (mid < t) res += query(s,t,mid+1,r,rt<<1|1);195 mans[rt] = res;196 while (mans[rt] > 9) mans[rt] -= 9;197 pushUpAns(rt);198 return res;199 }200 201 int main()202 {203 //freopen("test.in","r+",stdin);204 initial();205 int t, caseo = 1;206 scanf_(t);207 while(t--)208 {209 printf("Case #%d:\n",caseo ++);210 int n;211 scanf_(n);212 build(1,n,1);213 int Q;214 scanf_(Q);215 while(Q--)216 {217 memset(ans,0,sizeof(ans));218 memset(lans,0,sizeof(lans));219 memset(rans,0,sizeof(lans));220 memset(mans,0,sizeof(mans));221 int l,r;222 scanf_(l),scanf_(r);223 query(l,r,1,n,1);224 int tot = 0;225 for (int i = 9; i >= 0; i --)226 if (ans[1][i] && tot < 5)227 {228 tot ++;229 //tot == 5?printf("%d\n",i):printf("%d ",i);230 if (tot == 5)231 printf_(i),putchar('\n');232 else printf_(i),putchar(' ');233 }234 while(tot < 5)235 {236 tot ++;237 //tot == 5?printf("-1\n"):printf("-1 ");238 if (tot == 5)239 puts("-1");240 else241 {242 putchar('-');243 putchar('1');244 putchar(' ');245 }246 }247 }248 if (t) printf("\n");249 }250 return 0;251 }

　　噗。。。然后第二天上午终于找到哪儿超时了（我说怎么加了打表优化和输入输出优化还超T_T），竟然是开始回答询问时的那四个memset T_T，然后恍然大悟。。。我竟然sb的给ans也建了颗线段树！活该作死啊。。。T_T。。。

　　然后把ans改为节点，加上打表优化、输入输出外挂后终于A了T_T  （速度还不是很快啊。。。网上找了个程序1100MS呜呜。。。）：

6851969 2012-10-02 15:18:54 Accepted 4351 1546MS 32140K 6320 B G++ Abandon.burning
HDU 4351 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #define MID(x,y) ((x+y)>>1) 13 14 using namespace std; 15 const int maxn = 100100; 16 int mmax[maxn<<2],lsum[maxn<<2][10],rsum[maxn<<2][10],ssum[maxn<<2][10]; 17 int mul[10][10]; //合并i,j打表优化 18 19 struct ANS 20 { 21 int ls[10], rs[10]; 22 int res[10]; 23 int all; 24 ANS() 25 { 26 memset(ls,0,sizeof(ls)); 27 memset(rs,0,sizeof(rs)); 28 memset(res,0,sizeof(res)); 29 all = 0; 30 } 31 }; 32 33 void initial() 34 { 35 for (int i = 0; i < 10; i ++) 36 for (int j = 0; j < 10; j ++) 37 { 38 int k = i + j; 39 while (k > 9) 40 k -= 9; 41 mul[i][j] = k; 42 } 43 } 44 //外挂优化。。。 45 inline void scanf_(int &num) 46 { 47 char in; 48 bool neg = false; 49 while(((in = getchar()) > '9' || in <'0') && in != '-') ; 50 if(in == '-') 51 { 52 neg = true; 53 while((in = getchar()) >'9' || in < '0'); 54 } 55 num = in - '0'; 56 while(in = getchar(),in >= '0' && in <= '9') 57 num *= 10, num += in - '0'; 58 if(neg) 59 num = 0 - num; 60 } 61 inline void printf_(int num) 62 { 63 if(num < 0) 64 { 65 putchar('-'); 66 num =- num; 67 } 68 int ans[10],top = 0; 69 while(num != 0) 70 { 71 ans[top ++] = num % 10; 72 num /= 10; 73 } 74 if(top == 0) 75 putchar('0'); 76 for(int i = top - 1; i >= 0; i --) 77 { 78 char ch = ans[i] + '0'; 79 putchar(ch); 80 } 81 //putchar('\n'); 82 } 83 84 //线段树部分 85 inline void pushUp(int rt) 86 { 87 for (int i = 0; i < 10; i ++) 88 { 89 lsum[rt][i] = lsum[rt<<1][i]; 90 rsum[rt][i] = rsum[rt<<1|1][i]; 91 ssum[rt][i] = (ssum[rt<<1][i] == 1)?1:ssum[rt<<1|1][i]; 92 } 93 //修改区间和数字根 94 int k = mul[mmax[rt<<1]][mmax[rt<<1|1]]; 95 mmax[rt] = k, ssum[rt][k] = 1; 96 97 for (int i = 0; i < 10; i ++) 98 { 99 //右前缀+区间和扩展前缀数字根和子区间数字根100 if (lsum[rt<<1|1][i])101 {102 int k = mul[mmax[rt<<1]][i];103 lsum[rt][k] = 1, ssum[rt][k] = 1;104 }105 //左后缀+区间和扩展后缀数字根和子区间数字根106 if (rsum[rt<<1][i])107 {108 int k = mul[mmax[rt<<1|1]][i];109 rsum[rt][k] = 1, ssum[rt][k] = 1;110 111 //左后缀+右前缀扩展子区间数字根112 for (int j = 0; j < 10; j ++)113 if (lsum[rt<<1|1][j])114 {115 int k = mul[i][j];116 ssum[rt][k] = 1;117 }118 }119 }120 }121 122 inline void pushUpAns(int rt,ANS &p,ANS &lp,ANS &rp)123 {124 //查询时也要合并左右区间...125 for (int i = 0; i < 10; i ++)126 {127 p.ls[i] = lp.ls[i];128 p.rs[i] = rp.rs[i];129 p.res[i] = (lp.res[i] == 1)?1:rp.res[i];130 }131 for (int i = 0; i < 10; i ++)132 {133 if (rp.ls[i])134 {135 int k = mul[lp.all][i];136 p.ls[k] = 1, p.res[k] = 1;137 }138 if (lp.rs[i])139 {140 int k = mul[rp.all][i];141 p.rs[k] = 1, p.res[k] = 1;142 }143 if (lp.rs[i])144 for (int j = 0; j < 10; j ++)145 if (rp.ls[j])146 {147 int k = mul[i][j];148 p.res[k] = 1;149 }150 }151 }152 153 void build(int l,int r,int rt)154 {155 if (l == r)156 {157 mmax[rt] = 0;158 for (int i = 0; i < 10; i ++)159 {160 lsum[rt][i] = 0;161 rsum[rt][i] = 0;162 ssum[rt][i] = 0;163 }164 int a;165 scanf_(a);166 //scanf("%d",&a);167 if (!a) { mmax[rt] = 0; lsum[rt][0] = 1; rsum[rt][0] = 1; ssum[rt][0] = 1; }168 else169 {170 a = a % 9;171 if (!a) { mmax[rt] = 9; lsum[rt][9] = 1; rsum[rt][9] = 1; ssum[rt][9] = 1; }172 else { mmax[rt] = a; lsum[rt][a] = 1; rsum[rt][a] = 1; ssum[rt][a] = 1; }173 }174 return ;175 }176 int mid = MID(l,r);177 build(l, mid, rt<<1);178 build(mid+1, r, rt<<1|1);179 pushUp(rt);180 }181 182 int query(int s,int t,int l,int r,int rt,ANS &p)183 {184 if (s <= l && r <= t)185 {186 for (int i = 9; i >= 0; i --)187 {188 if (ssum[rt][i])189 p.res[i] = 1;190 if (lsum[rt][i])191 p.ls[i] = 1;192 if (rsum[rt][i])193 p.rs[i] = 1;194 }195 p.all = mmax[rt];196 while (p.all > 9) p.all -= 9;197 return p.all;198 }199 int res = 0;200 int mid = MID(l,r);201 ANS lp,rp;202 if (s <= mid) res += query(s,t,l,mid,rt<<1,lp);203 if (mid < t) res += query(s,t,mid+1,r,rt<<1|1,rp);204 p.all = res;205 while (p.all > 9) p.all -= 9;206 pushUpAns(rt,p,lp,rp);207 return res;208 }209 210 int main()211 {212 // freopen("data.txt","r+",stdin);213 // freopen("ans.txt","w+",stdout);214 initial();215 int t, caseo = 1;216 scanf_(t);217 //scanf("%d",&t);218 while(t--)219 {220 printf("Case #%d:\n",caseo ++);221 int n;222 scanf_(n);223 //scanf("%d",&n);224 build(1,n,1);225 int Q;226 scanf_(Q);227 //scanf("%d",&Q);228 while(Q--)229 {230 ANS ans;231 int l,r;232 scanf_(l),scanf_(r);233 //scanf("%d%d",&l,&r);234 query(l,r,1,n,1,ans);235 int tot = 0;236 for (int i = 9; i >= 0; i --)237 if (ans.res[i] && tot < 5)238 {239 tot ++;240 //tot == 5?printf("%d\n",i):printf("%d ",i);241 if (tot == 5)242 printf_(i),putchar('\n');243 else printf_(i),putchar(' ');244 }245 while(tot < 5)246 {247 tot ++;248 //tot == 5?printf("-1\n"):printf("-1 ");249 if (tot == 5)250 puts("-1");251 else252 {253 putchar('-');254 putchar('1');255 putchar(' ');256 }257 }258 }259 if (t) printf("\n");260 }261 return 0;262 }

 

♥扫描线:这类题目需要将一些操作排序,然后从左到右用一根扫描线(当然是在我们脑子里)扫过去。最典型的就是矩形面积并,周长并等题

 

　　♠ (矩形面积并入门题)

　　问题抽象：矩形面积并

　　其他入门题： (就是这道题，不过POJ的数据比较弱...)、、(所有矩形底边都在一条水平线上)

　　思路：浮点数先要离散化; 对于一个矩形(x1, y1, x2, y2)，只取上边和下边，结构体ss[] 记录一条边的左右点坐标和距坐标轴的高度，再拿一个变量 ss[].s记录这条边是上边还是下边，下边记录为1，上边记录为-1。按高度排序，对横轴建树，从低到高扫描一遍。若下边，则加入线段树；若上边，则从线段树上去掉。用cnt表示该区间下边比上边多几条线段,sum代表该区间内被覆盖的长度总和。

　　这里线段树的一个结点并非是线段的一个端点,而是该端点和下一个端点间的线段,所以题目中r+1,r-1的地方要好好的琢磨一下。

　　可以去看看nocLyt的图解：

HDU 1542 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #define MID(x,y) ((x+y)>>1) 13 14 using namespace std; 15 const int maxn = 500; 16 double X[maxn]; 17 double sum[maxn<<2]; 18 int cnt[maxn<<2]; 19 20 struct Seg 21 { 22 double l,r,h; 23 int s; 24 Seg(){} 25 Seg(double a,double b,double c,int d):l(a),r(b),h(c),s(d){} 26 bool operator < (const Seg &cmp) const 27 { 28 return h < cmp.h; 29 } 30 }ss[maxn]; 31 32 void pushup(int rt,int l,int r) 33 { 34 if (cnt[rt]) sum[rt] = X[r+1] - X[l]; 35 else if (l == r) sum[rt] = 0; 36 else sum[rt] = sum[rt<<1] + sum[rt<<1|1]; 37 } 38 void update(int s,int t,int v,int l,int r,int rt) 39 { 40 if (s <= l && r <= t) 41 { 42 cnt[rt] += v; 43 pushup(rt,l,r); 44 return ; 45 } 46 int mid = MID(l,r); 47 if (s <= mid) update(s,t,v,l,mid,rt<<1); 48 if (mid < t) update(s,t,v,mid+1,r,rt<<1|1); 49 pushup(rt,l,r); 50 } 51 int binfind(double x,int n,double X[]) 52 { 53 int head = 0, tail = n - 1; 54 while(head <= tail) 55 { 56 int mid = MID(head,tail); 57 if (X[mid] == x) return mid; 58 if (X[mid] < x) head = mid + 1; 59 else tail = mid - 1; 60 } 61 return -1; 62 } 63 int main() 64 { 65 //freopen("data.txt","r+",stdin); 66 67 int cas = 1; 68 int n; 69 while(~scanf("%d",&n) && n) 70 { 71 int tot = 0; 72 while(n--) 73 { 74 double a,b,c,d; 75 scanf("%lf%lf%lf%lf",&a,&b,&c,&d); 76 X[tot] = a; 77 ss[tot ++] = Seg(a,c,b,1); 78 X[tot] = c; 79 ss[tot ++] = Seg(a,c,d,-1); 80 } 81 sort(X,X+tot); 82 sort(ss,ss+tot); 83 int ptot = 1; 84 for (int i = 1; i < tot ; i ++) //зјБъШЅжи 85 if (X[i]!=X[i-1]) X[ptot ++] = X[i]; 86 87 //build(1,ptot,1); 88 memset(cnt , 0 , sizeof(cnt)); 89 memset(sum , 0 , sizeof(sum)); 90 double res = 0; 91 for (int i = 0; i < tot - 1; i ++) 92 { 93 int l = binfind(ss[i].l, ptot, X); 94 int r = binfind(ss[i].r, ptot, X) - 1; 95 if (l <= r) update(l, r, ss[i].s, 0, ptot-1 , 1); 96 res += sum[1] * (ss[i+1].h - ss[i].h); 97 } 98 printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++ , res); 99 }100 101 return 0;102 }

 

　　♠ ()

　　问题抽象：矩形面积并

　　贴矩形海报，每次贴前都要在海报中剪个小的矩形洞，然后求面积并。思路很简单，把单个海报剪掉一个洞后看成四个小海报就行了，分成四个小矩形时要注意下边界处理问题，然后直接套HDU 1542的模板1Y了 =.=。。。

HDU 3265 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #define MID(x,y) ((x+y)>>1) 13 14 using namespace std; 15 const int maxn = 400100; 16 int X[maxn]; 17 long long sum[maxn<<2]; 18 int cnt[maxn<<2]; 19 20 struct Seg 21 { 22 int l,r,h; 23 int s; 24 Seg(){} 25 Seg(int a,int b,int c,int d):l(a),r(b),h(c),s(d){} 26 bool operator < (const Seg &cmp) const 27 { 28 return h < cmp.h; 29 } 30 }ss[maxn]; 31 32 void pushup(int rt,int l,int r) 33 { 34 if (cnt[rt]) sum[rt] = X[r+1] - X[l]; 35 else if (l == r) sum[rt] = 0; 36 else sum[rt] = sum[rt<<1] + sum[rt<<1|1]; 37 } 38 void update(int s,int t,int v,int l,int r,int rt) 39 { 40 if (s <= l && r <= t) 41 { 42 cnt[rt] += v; 43 pushup(rt,l,r); 44 return ; 45 } 46 int mid = MID(l,r); 47 if (s <= mid) update(s,t,v,l,mid,rt<<1); 48 if (mid < t) update(s,t,v,mid+1,r,rt<<1|1); 49 pushup(rt,l,r); 50 } 51 int binfind(int x,int n,int X[]) 52 { 53 int head = 0, tail = n - 1; 54 while(head <= tail) 55 { 56 int mid = MID(head,tail); 57 if (X[mid] == x) return mid; 58 if (X[mid] < x) head = mid + 1; 59 else tail = mid - 1; 60 } 61 return -1; 62 } 63 int main() 64 { 65 //freopen("data.txt","r+",stdin); 66 int n; 67 while(~scanf("%d",&n) && n) 68 { 69 int tot = 0; 70 while(n--) 71 { 72 int x1,y1,x2,y2,x3,y3,x4,y4; 73 scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4); 74 if (x1 < x3) 75 { 76 X[tot] = x1; 77 ss[tot++] = Seg(x1,x3,y3,1); 78 X[tot] = x3; 79 ss[tot++] = Seg(x1,x3,y4,-1); 80 } 81 if (x4 < x2) 82 { 83 X[tot] = x4; 84 ss[tot++] = Seg(x4,x2,y3,1); 85 X[tot] = x2; 86 ss[tot++] = Seg(x4,x2,y4,-1); 87 } 88 if (y4 < y2) 89 { 90 X[tot] = x1; 91 ss[tot++] = Seg(x1,x2,y4,1); 92 X[tot] = x2; 93 ss[tot++] = Seg(x1,x2,y2,-1); 94 } 95 if (y1 < y3) 96 { 97 X[tot] = x1; 98 ss[tot++] = Seg(x1,x2,y1,1); 99 X[tot] = x2;100 ss[tot++] = Seg(x1,x2,y3,-1);101 }102 }103 sort(X,X+tot);104 sort(ss,ss+tot);105 int ptot = 1;106 for (int i = 1; i < tot ; i ++)107 if (X[i]!=X[i-1]) X[ptot ++] = X[i];108 109 memset(cnt , 0 , sizeof(cnt));110 memset(sum , 0 , sizeof(sum));111 long long res = 0;112 for (int i = 0; i < tot - 1; i ++)113 {114 int l = binfind(ss[i].l, ptot, X);115 int r = binfind(ss[i].r, ptot, X) - 1;116 if (l <= r) update(l, r, ss[i].s, 0, ptot-1 , 1);117 res += sum[1] * (ss[i+1].h - ss[i].h);118 }119 printf("%I64d\n",res);120 }121 122 return 0;123 }

 

♥二维线段树:此类线段树没什么意思，就是代码量加倍了而已，运用范围也没一维线段树广，会写就行了

　　二维线段树需要有两个维度，所以实现它的最基本思想就是树中套树。假设有一个矩形横坐标范围1—n，纵坐标范围1—m。我们可以以横坐标为一个维度，建立一棵线段树，假设为tree1，在这棵树的每个节点中以纵坐标建立一棵线段树，设为tree2，假设我们在tree1所处在的节点的的横坐标范围为l,r，那么该节点表示的矩形范围为横坐标为l—r，纵坐标范围为1—m。若我们正处在该节点中tree2的某个节点，该节点的纵坐标范围为d—u，那么tree2中的这个节点所代表的矩形范围，横坐标l—r，纵坐标d—u。所以我们看到，树套树&&二维线段树只要理解其思想就会发现其实并不难。

 

　　♠ (二维线段树入门)

　　因为有两个限制范围，所以需要二维的线段树。也没什么好说的地方。

　　需要注意几个问题：1.初始化sum = -1，不然所有的返回结果都是>=0的数，查找不到的情况不好判断。

　　　　　　　　　　　2.坐标左小右大（因为这个白白贡献几次WA擦。。。）

　　　　　　　　　　　3.有可能存在同一身高、活泼度的人，所以更新时不是直接赋值而是选个缘分值最大的。

HDU 1823 
1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #define MID(x,y) ((x+y)>>1) 13 14 using namespace std; 15 16 const int maxn1 = 105; 17 const int maxn2 = 1050; 18 int sum[maxn1<<2][maxn2<<2]; 19 int n1 = 100, n2 = 1000; 20 21 void build() 22 { 23 memset(sum,-1,sizeof(sum)); 24 } 25 void update2(int p,int c,int l,int r,int rt1,int rt2) 26 { 27 if (l == p && r == p) 28 { 29 sum[rt1][rt2] = max(sum[rt1][rt2], c); //重要！：有可能存在身高、活泼度一样的美女，要选缘分值高的 30 return ; 31 } 32 33 int mid = MID(l,r); 34 if (p <= mid) update2(p,c,l,mid,rt1,rt2<<1); 35 else update2(p,c,mid+1,r,rt1,rt2<<1|1); 36 sum[rt1][rt2] = max(sum[rt1][rt2<<1],sum[rt1][rt2<<1|1]); 37 } 38 void update1(int h,int p,int c,int l,int r,int rt) //h身高，p活泼度 39 { 40 update2(p,c,0,n2,rt,1); 41 if (l == h && r == h) 42 return ; 43 int mid = MID(l,r); 44 if (h <= mid) update1(h,p,c,l,mid,rt<<1); 45 else update1(h,p,c,mid+1,r,rt<<1|1); 46 } 47 int query2(int p1,int p2,int l,int r,int rt1,int rt2) 48 { 49 if (p1 <= l && r <= p2) 50 { 51 return sum[rt1][rt2]; 52 } 53 int mid = MID(l,r); 54 int res = -1; 55 if (p1 <= mid) res = max(res, query2(p1,p2,l,mid,rt1,rt2<<1)); 56 if (mid < p2) res = max(res, query2(p1,p2,mid+1,r,rt1,rt2<<1|1)); 57 return res; 58 } 59 int query1(int h1,int h2,int p1,int p2,int l,int r,int rt) 60 { 61 if (h1 <= l && r <= h2) 62 return query2(p1,p2,0,n2,rt,1); 63 int mid = MID(l,r); 64 int res = -1; 65 if (h1 <= mid) res = max(res, query1(h1,h2,p1,p2,l,mid,rt<<1)); 66 if (mid < h2) res = max(res, query1(h1,h2,p1,p2,mid+1,r,rt<<1|1)); 67 return res; 68 } 69 int main() 70 { 71 //freopen("data.txt","r+",stdin); 72 73 int m; 74 while(scanf("%d",&m),m) 75 { 76 build(); 77 while(m--) 78 { 79 char s[2]; 80 scanf("%s",s); 81 if (s[0] == 'I') 82 { 83 int h; 84 double p,num; 85 scanf("%d%lf%lf",&h,&p,&num); 86 update1(h,int(p*10),int(num*10),n1,n1+100,1); 87 } 88 else 89 { 90 int h1,h2; 91 double p1,p2; 92 scanf("%d%d%lf%lf",&h1,&h2,&p1,&p2); 93 if (h1 > h2) swap(h1,h2); 94 if (p1 > p2) swap(p1,p2); 95 int res = query1(h1,h2,int(p1*10),int(p2*10),n1,n1+100,1); 96 if (res < 0) printf("-1\n"); 97 else printf("%.1lf\n",res*1.0/10.0); 98 } 99 }100 }101 102 return 0;103 }

 

(未完待续...)

转载于:https://www.cnblogs.com/AbandonZHANG/archive/2012/09/15/2631928.html

你可能感兴趣的文章
初遇GitHub
查看>>
[C# 网络编程系列]专题八：P2P编程
查看>>
Jsの练习-数组常用方法 -forEach()
查看>>
动态绑定treeview的方法
查看>>
jvm参数
查看>>
3-1 案例环境初始化
查看>>
读《构建之法》第四章和十七章有感
查看>>
01背包
查看>>
开发一个12306网站要多少钱？技术分析12306合格还是不合格
查看>>
Selenium 入门到精通系列：六
查看>>
HTTP与TCP的区别和联系
查看>>
android 实现2张图片层叠效果
查看>>
我个人所有的独立博客wordpress都被挂马
查看>>
html5——动画案例（时钟）
查看>>
调用Android系统“应用程序信息（Application Info）”界面
查看>>
ios中用drawRect方法绘图的时候设置颜色
查看>>
数据库中的外键和主键理解
查看>>
个人博客03
查看>>
Expression<Func<T,TResult>>和Func<T,TResult>
查看>>
文件缓存
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-13 11:09:10   当前IP: 18.219.86.191   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我