Description

给定了一个长度为\(n\)的数列和若干个询问，每个询问是关于数列的区间表示数列的第\(l\)个数到第\(r\)个数)，首先你要统计该区间内大于等于\(a\)，小于等于\(b\)的数的个数，其次是所有大于等于\(a\)，小于等于\(b\)的，且在该区间中出现过的数值的个数。

\(n,m \leq 10^5\)

Solution

非常简单的莫队题目

追求更优的复杂度，可以采用\(cdq\)分治：

我们发现其实原题可以简化成一个三维数点

• \(L \leq i\leq R\)
• \(A\leq a[i] \leq B\)
• \(pre[i]\leq L-1\)

于是把值离散一下，直接上\(cdq\)就行了

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)>(b)?(b):(a))#define reg registerinline 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<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}const int MN=1e5+5;struct Node{    int x,y,z,sign,id;    bool operator < (const Node&_)const    {        if(z^_.z) return z<_.z;        return id<_.id;    }}a[MN*5],b[MN*5];int ans1[MN],ans2[MN],tot;int t[MN];void C(int x,int val){for(;x<=MN;x+=(x&-x))t[x]+=val;}int G(int x){int r=0;for(;x;x-=(x&-x))r+=t[x];return r;}void cdq(int l,int r){    if(l==r) return;    reg int i,j,p=l,mid=(l+r)>>1;    cdq(l,mid);cdq(mid+1,r);    for(i=l,j=mid+1;i<=mid||j<=r;)        if(j>r||(i<=mid&&(a[i].y
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！