区间内x的出现个数(主席树)

时间：2023-03-10 02:38:46
区间内x的出现个数(主席树)

题目大概：求区间内x出现的次数

出题人yjy

Description

ZJK 给你一个长度为 n 的数列和 m 次询问，每次询问从第 l 个到第 r 个数中，数 x 出现
了多少次。
Input
第一行一个整数 n，
第二行 n 个整数，表示这个数列。
第三行一个整数 m，表示询问数。
下面 m 行，每行三个整数 l, r, x，表示询问[l, r]之间数 x 出现的次数
Output
对于每个询问操作，输出该询问的答案。答案之间用换行隔开，一共 m 行。
Example
6
1 1 2 3 3 1
8
1 6 1
3 5 3
3 5 2
2 6 1
1 3 3
2 6 3
2 6 4
1 6 2

3
2
1
2
0
2
0
1
Hint
涉及到的数列中所有数 x∈[1, 200000]
序列长度 n <= 100000
询问数 m <= 100000
注意：询问中有可能会询问不存在的数，但一定满足 x ∈ [1, 200000]

主席树板子嘛，比 第k大值 得板子还板子，至于主席树，有空再补一篇吧

add维护数出现的个数，n的范围20w，不用离散化

查询的时候，就一直查询，直到查询到叶节点，然后两点做差

ps：n不是树的大小范围，挂在这里(；′⌒`)

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 int n,m,root[MAXN],cut,a[MAXN],s[MAXN];

 struct data

 {

     int lc,rc,ans;

 }tree[MAXN*];

 void add(int &now,int last,int l,int r,int x)

 {

     now=++cut;

     tree[now].ans=tree[last].ans+;

     if(l==r) return ;

     tree[now].lc=tree[last].lc;

     tree[now].rc=tree[last].rc;

     int mid=(l+r)>>;

     if(x<=mid) add(tree[now].lc,tree[last].lc,l,mid,x);

     else add(tree[now].rc,tree[last].rc,mid+,r,x);

 }

 int query(int L,int R,int l,int r,int x)

 {

     if(l==r)return tree[L].ans-tree[R].ans;

     int mid=(l+r)>>;

     if(x<=mid)return query(tree[L].lc,tree[R].lc,l,mid,x);

     else return query(tree[L].rc,tree[R].rc,mid+,r,x);

 }

 int main()

 {

     int x,y,z,p=;

     scanf("%d",&n);

     for(int i=;i<=n;++i)

     {

         scanf("%d",&a[i]);

         p=max(p,a[i]);

     }

     for(int i=;i<=n;++i)

         add(root[i],root[i-],,p,a[i]);

     scanf("%d",&m);

     while(m--)

     {

         scanf("%d%d%d",&x,&y,&z);

         if(z>p) {

             printf("0\n");

             continue;

         }

         printf("%d\n",query(root[y],root[x-],,p,z));

     }

     return ;

 }




out1












in1












in2












out2


相关文章