PS:今天上午，非常郁闷，有很多简单基础的问题搞得我有些迷茫，哎，代码几天不写就忘。目前又不当COO，还是得用心记代码哦！

    转载请注明出处，感谢    by---cxlove

    

恐怖的莫队法算。。。觉感有了这个，是不是可以决解全部的区间查询但是无修改的目题

    

许也不是最优的，但是O(n*sqrt(n))全完也是可以实验的。

    

    

莫队法算：对于两个区间的查询[l1,r1] ,[l2,r2]如果每加增一个区间元素或者删除，都能做到O(1)的话

    

那么从[l1,r1]转移到[l2,r2]，暴力可以做到|l1-l2|+|r1-r2|，就是manhattan距离

    

莫队的论文始终没有找到，所以只是大致的了解下，应该是证明出结构出哈密尔顿路径是最优的。

    

但是可以用manhattan mst来结构，大约会是两倍，然后莫队证明出这样转移的限上是O(n*sqrt(n))。

    

所以对于这类无修改的区间查询说来

    

可以先将全部的区间，当作维二平面上的点，求一次manhattan mst，然后根据mst来行进转移

    

相邻的两个区间的查询转移，暴力决解。

    

 这里有

    每日一道理

时间好比一条小溪，它能招引我们奔向生活的海洋；时间如同一叶扁舟，它将帮助我们驶向理想的彼岸；时间犹如一支画笔，它会指点我们描绘人生的画卷。

#include 
     
        #include 
      
         #include 
       
          #include 
        
         #include 
         
          #define lowbit(x) (x&(-x)) #define LL long long using namespace std;  const int N = 50005;  struct Point{      int x,y,id;      bool operator<(const Point p)const{          return x!=p.x?x
          
           
            =1;i-=lowbit(i)) if(val
            
             =0;i--){ int pos=lower_bound(b,b+m,a[i])-b+1; //BIT中从1开始 int ans=ask(pos,m); if(ans!=-1) addedge(p[i].id,p[ans].id,dist(i,ans)); update(pos,p[i].x+p[i].y,i); } } sort(e,e+tot); for(int i=0;i
             
              r1) add(r1+1,r2); if(l2>l1) del(l1,l2-1); if(r2
              
               r1) del(r1+1,r2); if(l2>l1) add(l1,l2-1); if(r2
              
             
            
           
          
         
        
       
      
     

文章结束给大家分享下程序员的一些笑话语录： 　一边用着越狱的ip，一边拜乔帮主的果粉自以为是果粉，其实在乔帮主的眼里是不折不扣的叛徒。