wa/tle了三页才写出来。。。菜鸡果然是菜鸡

主席树

这个昨晚刚看的数据结构，敲的时候敲错了n多次。。
在树里，把数的版本号当作数组下标，树内记录每个区间内的数的出现次数，学过之后还是比较好理解的。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+10;
struct node{
    int l,r,sum;
}tree[maxn*40];
int cnt,root[maxn];
int n,m;
int a[maxn];
void insert(int l,int r,int pre,int &now,int val){
    tree[++cnt]=tree[pre];
    now=cnt;
    tree[now].sum++;
    if(l==r) return;
    int m=(l+r)>>1;
    if(val<=m) insert(l,m,tree[pre].l,tree[now].l,val);
    else insert(m+1,r,tree[pre].r,tree[now].r,val);
}

int query(int l,int r,int L,int R,int k,int val){
    if(r<=val) return tree[R].sum-tree[L].sum;
    int m=(l+r)>>1;
    if(val<=m) return query(l,m,tree[L].l,tree[R].l,k,val);
    else if(k>m) return query(m+1,r,tree[L].r,tree[R].r,k,val);
    else return query(l,m,tree[L].l,tree[R].l,k,m)+query(m+1,r,tree[L].r,tree[R].r,m+1,val);
}

int main()
{
    scanf("%d %d",&n,&m);
    int ss=0;
    for(int i=1;i<=n;i++) scanf("%d",a+i),ss=max(a[i],ss);
    for(int i=1;i<=n;i++){
        insert(1,ss,root[i-1],root[i],a[i]);
    }
    while(m--){
        int l,r,k;
        scanf("%d %d %d",&l,&r,&k);
        printf("%d\n",query(1,ss,root[l-1],root[r],1,k));
    }
    return 0;
}

离线+树状数组

平时很少做离线做orz。我是看了邓老师的题解之后写的，做法是：分别对每次询问的k值和ai进行排序，然后在树状数组上标记下这个位置是否对答案有没有贡献。
比如说，按照样例：1 2 3 4 5
现在，要查询的k为3，那么，对答案有贡献的为止就是i=1，2，3，那么，就在树状数组内把1、2、3位置（所有ai<=k的位置）标记为1，然后用树状数组求前缀和就可以了。
真正起作用的是排序：我们把查询按照k值进行了排序，比如这次查询的是3，那就把所有数组中ai<=3的全部位置标记到树状数组中。下次要查询5的时候，上次我们标记了3的，我们就不需要再去标记ai<=3的部分了，直接标记ai==4、ai==5的部分就行了，因为ai被排序了，所以，我们可以通过记下上一次ai<=3的时候标记到了排序后的ai数组的那一个位置，然后，从那个位置继续标记就好了，是分块的思想。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define lowbit(x) ((x)&-(x))
using namespace std;
const int maxn=1e5+10;
int tree[maxn];
int ans[maxn];
int n,m;
struct qs{
    int l,r,k,num;
};
struct ai{
    int pos,val;
    friend bool operator<(const ai&x,const ai&y){
        return x.val<y.val;
    }
};
bool cmp(qs a,qs b){
    return a.k<b.k;
}
vector<qs> ques;
vector<ai> as;
void modify(int x,int val){
    while(x<=n){
        tree[x]+=val;
        x+=lowbit(x);
    }
}

int query(int x){
    int res=0;
    while(x>0){
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        ai tmpp;
        scanf("%d",&tmpp.val);
        tmpp.pos=i;
        as.push_back(tmpp);
    }
    for(int i=1;i<=m;i++){
        int l,r,k;
        scanf("%d %d %d",&l,&r,&k);
        qs tmp={l,r,k,i};
        ques.push_back(tmp);
    }
    sort(ques.begin(),ques.end(),cmp);
    sort(as.begin(),as.end());
    int pre=0;
    int pree=0;
    for(int i=0;i<ques.size();i++){
        qs now=ques[i];
        if(now.k!=pre)
        {
            while(as[pree].val<=now.k&&pree<as.size()){
                modify(as[pree].pos,1);
                pree++;
            }
            pre=now.k;
        }
        ans[now.num]=query(now.r)-query(now.l-1);
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);

    return 0;
}

至于莫队嘛。。下次一定（逃