只是一些瞎想

没学过线段树，不会区间更新，不会做维护（我就是一条咸鱼

花了五分钟在网上看了一下线段树的思想，大概明白了怎么个用法，但是没有背模板也不会写

所以考虑用树状数组

用二维数组叠成线段树的样子

简单讲下想法：

核心：二维数组写线段树

　　　　第1层是目标数列；

　　　　第2层存储每相邻2项之和，第3层存储每相邻4项之和，以此类推...

　　　　第n层存储每相邻2^n项之和；

　　（题目要求1≤n,q≤100000不超过2^17,17*100000的矩阵可以完成）

一个简单的例子16 100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1add 1 1212 0 0 0 0 0 0 0 0 0 0 0 0 0 0 012 0 0 0 0 0 0 0 0 0 0 0 0 0 0 012 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 4 0 0 0 4 0 0 0 4 0 0 0 0 0 0 0 2 0 2 0 2 0 2 0 2 0 2 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0

 

　　每次 add 操作，对a数组对应元素+1，

　　满足a[i]==b[i]则置零, 找到tree数组底层对应元素，从该结点到根节点的路径都标记上+1；

　　访问路径结点通过数组下标的计算实现。

　　query操作麻烦一些，

　　一方面要判断能取到的最大段，另一方面要定位端点，把剩下的部分继续拆分。

　　通过一个l，r分别除一个整数div = 2^n，找到当前端点所在的区段，

　　div从上限开始，每次减半，

　　若可以取到当前大小的整段，把当前整段的权值加到res，并记录下断电，

　　对裁剪后两边的段进行相同操作，

因为区段（l，r）是连续的，每次断开断点为2^n，所以当前状态最多有两个不相接段；

另外当l，r为2^n点时可以有简化计算。

 

很遗憾的是这段代码仅通过了样例和部分测试组，所以并没有算过题

　　并且这种实现方法非常蹩脚 debug基本靠笔算

　　所以以后肯定老老实实背模板，也不会这么瞎鸡乱搞了

 

绿皮车代码仅供娱乐

1 #include 
     
       2 using namespace std; 3 typedef long long ll; 4  5 int sum[17][100006] = {
   0}; 6 int a[100006] = {
   0}; 7 int b[100006] = {
   0}; 8 char tell[6] = {
   0}; 9 10 int main(){11     int n , q ;12     int l , r ;13     cin >> n >> q;14     for (int i = 0;i
      
       > b[i];16     }//建树，完成输入17     while(q--){18         cin >> tell >> l >> r;19         if(tell[0]=='a'){
   //add操作20             for(int i = l-1;i
       
        =b[i]){
   //a累加到b时23                     for(int j = 0,k = 1;j<17;j++){
   　　　　　　　　　　　　　　　　//该节点到根节点路径上标记+124                         sum[16-j][i/k*k]++;25                         k*=2;26                     }27                     a[i] = 0;//a置零28                 }29             }30         }31         else if(tell[0]=='q'){
   //query操作32             bool s1 = 0;//端点是否截断在2^n位置33             int res = 0;//结果34             int l1 = -1 , r1 = -1;//拆分后用的新断点35             for(int i = 0,div= 65536;i<17;i++){
   　　　　　　　　　　　　　　　　//div从2^16开始，每次减半36                 if(l1==-1 && r1==-1){
   　　　　　　　　　　　　　　　　//判断是否被截取过37                     if(l/div==0 && l/div+1 < r/div){
                              //能截出当前最大段时38                         l1 = l/div+1;                        39                         r1 = r/div;        40                         for(int j = l1; j
        
         >= 1;//div减半91             }92             cout<
         
          <
         
        
       
      
     

带debug输出的版本，供自己以后心情好了翻出来改

1 #include 
      
         2 #include 
       
          3 using namespace std;  4   5 typedef long long ll;  6   7 int sum[17][100006] = {
    0};  8 int a[100006] = {
    0};  9 int b[100006] = {
    0}; 10 char tell[6] = {
    0}; 11  12 int main() 13 { 14     int n , q ; 15     int l , r ; 16     cin >> n >> q; 17     for (int i = 0;i
        
         > b[i]; 20     } 21     while(q--) 22     { 23         cin >> tell >> l >> r; 24         if(tell[0]=='a') 25         { 26             for(int i = l-1;i
         
          =b[i]) 30                 { 31                     for(int j = 0,k = 1;j<17;j++) 32                     { 33                         sum[16-j][i/k*k]++; 34                         k*=2; 35                     } 36                     a[i] = 0; 37                 } 38                      39             } 40             for(int j = 0;j<17;j++)                  // 41                     { 42                         for(int k = 0;k<16;k++) 43                             cout<
          
           <
           
            <<" "; 44 cout<
            
             >= 1;136 }137 cout<
             
              <