MY（一名蒟蒻）
2021-08-01 16:24:37
不能让卡老师的题解在第一篇！
SP3266 KQUERY - K-query
这题有一个强制在线的版本，那我们就直接使用在线算法解决这题！
我会主席树！不会分块。
以下摘自本人的题解 CF840D 【Destiny】，根据本题有调整。
由于这题非常模板所以我来介绍一下这玩意是啥。
以下摘自本人的题解 P6166 【[IOI2012]scrivener】
主席树，又名函数式线段树。由于发明人黄嘉泰的名字缩写和某位中国共产党领导人是一样的，故名主席树。
实现可持久化使用复制节点的方式，由于一次修改最多修改
又叫可持久化线段树，顾名思义可持久。
这个东西可以在一个数列中挖出一段来做
本题依靠权值线段树。
就是节点维护的不是区间的信息，而是值域上的信息。
每一个节点对应的是值域上的一段区间。
所以离散化是权值线段树经典操作。
边插入边建树，每次对树的形态产生更改时复制节点。
这里不能再使用线段树访问左右儿子的方式，要记录下每个节点的左右儿子。
插入时从内存池中取一块内存给复制的节点，每一次插入建立在上一个版本上。
因为这题权值线段树每个数字的贡献是所在区间的个数加一，所以如果我们用
对于每一个询问的数字，找到第一个比它大的数字在权值线段树中的位置，然后统计这个数及它右边一共有多少个数字即为答案。
实际上就是
递归的时候要把区间的左右端点一起传下去，注意这里的区间指的是数列上的区间。
值域很大，要离散化。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=3e4+10;
int n,cnt,rt[N],a[N],v[N];
struct node {int sum,l,r;} hjt[N << 4];
inline int clone(int o) {hjt[++cnt]=hjt[o]; return cnt;}//复制节点
int build(int o,int l,int r,int p)
{
o=clone(o); hjt[o].sum++;
if(l == r) return o;
int mid=(l+r) >> 1;
if(p <= mid) hjt[o].l=build(hjt[o].l,l,mid,p);
else hjt[o].r=build(hjt[o].r,mid+1,r,p);
return o;
}
int query(int l,int r,int L,int R,int p)
{
if(l == r) return hjt[R].sum-hjt[L].sum;
int mid=(l+r) >> 1;
if(p <= mid) return hjt[hjt[R].r].sum-hjt[hjt[L].r].sum+query(l,mid,hjt[L].l,hjt[R].l,p);
return query(mid+1,r,hjt[L].r,hjt[R].r,p);
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
int m,l,r,x,q;
scanf("%d",&n);
for(int i=1;i<=n;i++) {scanf("%d",&a[i]); v[i]=a[i];}
sort(v+1,v+1+n); m=unique(v+1,v+1+n)-v;//离散化
for(int i=1;i<=n;i++) rt[i]=build(rt[i-1],1,m-1,lower_bound(v+1,v+m,a[i])-v);
scanf("%d",&q);
while(q--)
{
scanf("%d%d%d",&l,&r,&x);
x=upper_bound(v+1,v+m,x)-v;//这里就直接upper_bound啦
if(x == m) puts("0");//越界
else printf("%d\n",query(1,m-1,rt[l-1],rt[r],x));
}
// fclose(stdin); fclose(stdout);
return 0;
}