区间加和区间和查询  之前作为线段树入门写过 这次用分块写一下 

区间主要就是两种情况 在同一个块or不同块。整块的区域我们只要成段更新就好了，反之暴力更新~

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #define FIN freopen("input.txt","r",stdin) 9 #define ll long long10 #define mod 100000000711 #define lson l,m,rt<<112 #define rson m+1,r,rt<<1|113 const int maxn = 105000+5;14 using namespace std;15 int q[maxn];16 int belong[maxn],l[maxn],r[maxn];17 ll sum[maxn],add[maxn];18 int n;19 void build(){20 int block=sqrt(n);21 if(block==0) block=1;22 int tot=n/block;23 if(n%block!=0)tot++;24 for(int i=1;i<=n;i++){25 belong[i]=(i-1)/block+1;26 }27 for(int i=1;i<=tot;i++){28 l[i]=(i-1)*block+1;29 r[i]=i*block;30 for(int j=l[i];j<=(i==tot?n:r[i]);j++)31 sum[i]+=q[j];32 }33 r[tot]=n;34 }35 void update(int x,int y,int c){36 if(belong[x]==belong[y]){37 for(int i=x;i<=y;i++){38 q[i]+=c;sum[belong[x]]+=c;39 }40 }else {41 for(int i=x;i<=r[belong[x]];i++){42 q[i]+=c;sum[belong[x]]+=c;43 }44 for(int i=l[belong[y]];i<=y;i++){45 q[i]+=c;sum[belong[y]]+=c;46 }47 for(int i=belong[x]+1;i
            
           
          
         
        
       
      

 

 区间第k大 之前主席树入门写过

思路：我们分块后，块内排序，然后每次我们二分数组的下标。每次对于二分的值，check下L到R区间里值是第几大，最后更新下最大值就好了。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define FIN freopen("input.txt","r",stdin)#define ll long long#define mod 1000000007#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int maxn = 100000+5;using namespace std;int q1[maxn],q2[maxn],q3[maxn];int belong[maxn],l[maxn],r[maxn];int n;void build(){ int block=sqrt(n); if(block==0) block=1; int tot=n/block; if(n%block) tot++; for(int i=1;i<=n;i++){ belong[i]=(i-1)/block+1; } for(int i=1;i<=tot;i++){ l[i]=(i-1)*block+1; r[i]=i*block; if(i==tot) r[i]=n; sort(q1+l[i],q1+r[i]+1); }}int check(int L,int R,int val){ int ans=0; if(belong[L]==belong[R]){ for(int i=L;i<=R;i++) if(q2[i]
             
              >1; if(q1[m]
              
               >1; if(check(L,R,q3[m])
              
             
            
           
          
         
        
       
      

 

 

思路：线段不想交，意味着后面的组成的线段斜率要比前面大即可，每次操作我们更新当前的块，然后每次我们只要求出大于等于前一块的最高值的数量，累加即可。

#include
      
       #define FIN freopen("input.txt","r",stdin)#define ll long long#define mod 1000000007#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int maxn = 100000+5;using namespace std;int belong[maxn],tot;struct node{    int l,r;    vector
       
         v;}p[maxn];double H[maxn];int n,m;void build(){    int k=sqrt(n);    tot=n/k;    if(n%k) tot++;    for(int i=1;i<=n;i++){     belong[i]=(i-1)/k+1;    }    for(int i=1;i<=tot;i++){        p[i].l=(i-1)*k+1;        p[i].r=i*k;    }    p[tot].r=n;}int solve(int x,int h){    int to=belong[x];    H[x]=1.0*h/x;    double mx=0.0;    p[to].v.clear();    for(int i=p[to].l;i<=p[to].r;i++){        if(H[i]>mx){            mx=H[i];            p[to].v.push_back(H[i]);        }    }    mx=0.0;    int ans=0;    for(int i=1;i<=tot;i++){        if(p[i].v.size()==0) continue;    ans+=p[i].v.end()-upper_bound(p[i].v.begin(),p[i].v.end(),mx);    mx=max(mx,*p[i].v.rbegin());    }    return ans;}int main(){    #ifndef ONLINE_JUDGE        FIN;    #endif    scanf("%d %d",&n,&m);    build();    for(int i=1;i<=m;i++){        int x,h;        scanf("%d %d",&x,&h);        printf("%d\n",solve(x,h));    }}