数据结构题

　　链接：https://ac.nowcoder.com/acm/contest/917/H
来源：牛客网

get(l,r,x)表示求a[l]~a[r]中x出现了几次，他很快推出了规律，

但正当他把这道题录入电脑是发现作为一个蒟蒻的他不会打latex也没找到数学符号(主要是懒)，

所以他省略了那个

为了防数据过大，你要对20180623取模

不保证l<r,l1<r1,遇到这种情况，请先交换一下

注:本系列题不按难度排序哦

输入描述:

第一行一个n,m 接下来一行n个数表示a[i] 接下来m行，每行l,r,l1,r1,x，表示求get(l,r,x)*get(l1,r1,x)

输出描述:

3×m行，先输出get(l,r,x),再输出get(l1,r1,x)，再输出get(l,r,x)*get(l1,r1,x)

示例1

输入

复制

5 1
2 2 2 2 2
1 5 1 3 2

输出

复制

5
3
15


维护区间内 k数的个数  
正解是主席树 

可以用二分解决。。

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
const int mod=20180623;
const int N=1e5+5;
int n,m;
vector<int>V[N];

int main()
{
    RII(n,m);
    rep(i,1,n)
    {
        int x;RI(x);
        V[x].pb(i);
    }
    rep(i,1,m)
    {
        int u,v,u1,v1,k;
        RIII(u,v,u1);RII(v1,k);
        if(u>v)swap(u,v);
        if(u1>v1)swap(u1,v1);
        int ans1=upper_bound(V[k].begin(),V[k].end(),v)-lower_bound(V[k].begin(),V[k].end(),u);
        ans1%=mod;
        int ans2=upper_bound(V[k].begin(),V[k].end(),v1)-lower_bound(V[k].begin(),V[k].end(),u1);
        ans2%=mod;
        cout<<ans1<<endl<<ans2<<endl<<ans1*ans2%mod<<endl;

    }

    return 0;
}

View Code