/ Vijos / 题库 / 漫长的等待 1923

题目链接
https://www.vijos.org/p/1923

/ Vijos / 题库 /
漫长的等待
描述

曾经有一段时间，或许有5年，甚至更长吧。我与木姑娘失去了联系，怎么也联系不上。
那一段日子真的很艰难，我却总是能想起她。
细细数来，从我一声不吭离开，到再次见到她，过去了n天。每天都会不止一次想起她的身影。其中第i天会想起来她ai次。
再次相遇的时候，我向她坦白这一点。她不信。
她给我提出了m个问题，每次都是问我“从第l天到第r天中，有几天你想了我至少k次，却不超过w次？”
格式

输入格式

第一行2个整数n和m(1<=n<=100000,1<=m<=1000000)
之后一行给出n个数a1,a2,…,an
之后m行每行给出4个整数，依次为l,r,k,w
输出格式

输出m行对应m次询问的答案
样例1

样例输入1

10 5
1 2 3 4 1 2 5 3 2 4
1 4 1 3
1 4 1 4
1 4 2 10
1 10 1 2
1 10 1 3
Copy
样例输出1

3
4
3
5
7
Copy
限制

30％的数据，n<=3000，m<=3000。
50％的数据，n<=50000，m<=100000。
100%的数据，n<=100000，m<=1000000。
1<=ai<=1000000000

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 200002
#define M 2000002
using namespace std;
int L[M],R[M],cnt,head[N],no[M],nex[M];
int a[N],b[N],ans[M],tree[N];
int n;
int m,tot;
inline void push(int l,int r,int t,int num){
    L[++tot]=l;
    R[tot]=r;
    no[tot]=num;
    nex[tot]=head[t];
    head[t]=tot;
}
inline int lowbit(int x) {
    return x&-x;
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline bool cmp(int a,int b){
  return a<b;}
inline void add(int k){
    for(int i=k;i<=n;i+=lowbit(i)) tree[i]++;
}
inline int ask(int k){
    int res=0;
    for(int i=k;i>0;i-=lowbit(i)) res+=tree[i];
     return res;
}
int main(){
    n=read();
    m=read();
   int l,r,k,w;
   for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];//离散化
   for(int i=1;i<=m;i++){
        l=read();
        r=read();
        k=read();
        w=read();
        if(l>r) swap(l,r);
        if(k>w) swap(k,w);
        push(k,w,l-1,i);
        push(k,w,r,i);
    }
    sort(b+1,b+n+1,cmp);
   int len=unique(b+1,b+n+1)-b-1;//离散化
   for(int i=1;i<=n;i++){
       add(lower_bound(b+1,b+len+1,a[i])-b);
       for(int j=head[i];j;j=nex[j]){
           l=lower_bound(b,b+len+1,L[j])-b;
           r=lower_bound(b,b+len+1,R[j])-b;
           if(R[j]<b[r]) r--;
            if(ans[no[j]]){
                ans[no[j]]=ask(r)-ask(l-1)-ans[no[j]];
            }
            else{
                ans[no[j]]=ask(r)-ask(l-1);
            }
        }
    }

    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }
}

这是我到现在做过的最好的树状数组的题~~~强烈推荐