祎隋

Poklon
Description有一个长度为 n 的序列,每个数的范围在 0 到 $10^9$ 之内。你有 Q 个询问,给出...
扫描右侧二维码阅读全文
15
2019/02

Poklon

Description

有一个长度为 n 的序列,每个数的范围在 0 到 $10^9$ 之内。
你有 Q 个询问,给出 l, r,问这个序列中区间 l 到 r 中恰好出现了两次的数字的个数。序
列的下标从 1 开始。

Input

第一行两个整数 n 和 Q,接下来一行 n 个整数,表示这个序列。
接下来 Q 行,每行两个整数 l, r 表示询问的区间。
40% 的数据- n, Q ≤ 5000。
100% 的数据-1 ≤ n, Q ≤ 500000。

Output

Q 行,每行一个整数表示答案

Sample Input

5 2
1 1 2 2 3
1 1
1 5

Sample Output

0
2

Hint

时间限制:5s
空间限制:512MB

Solution

正解貌似是二维树状数组???没听懂orz。。。思想跟以前一道很类似,记录每一个数前面一个相同的和后面一个相同的,当区间包含l[i],i或i,r[i]时就会有贡献,从而以l为横轴,r为竖轴建立坐标系,每次修改就是一块矩形的加1,然后查询就对于(l,r)的点值。
<font color=red>有时间一定要了解下qwq</font>

然后貌似用莫队可以随随便便过,直接开始离散化一下,然后莫队一波就欧克了,O($n\sqrt{n}$)还是能过的。

上代码:

#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
int n,q,a[maxn],blog[maxn],t[maxn],c[maxn];
int calc=0;
struct node{
    int l,r,id,ans;
    friend bool operator <(node a,node b){
        if(blog[a.l]==blog[b.l]) return a.r<b.r;
        else return a.l<b.l;
    }
}nd[maxn];
bool cmp(node a,node b){
    return a.id<b.id;
}
void update1(int i){
    c[a[i]]--;
    if(c[a[i]]==1) calc--;
    if(c[a[i]]==2) calc++;
}
void update2(int i){
    c[a[i]]++;
    if(c[a[i]]==2) calc++;
    if(c[a[i]]==3) calc--;
}
void init(){
    scanf("%d%d",&n,&q);
    int blo=sqrt(n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),blog[i]=(i-1)/blo+1,t[i]=a[i];
    sort(t+1,t+n+1);
    int cnt=unique(t+1,t+n+1)-t-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(t+1,t+cnt+1,a[i])-t;
    }
    for(int i=1;i<=q;i++) scanf("%d%d",&nd[i].l,&nd[i].r),nd[i].id=i;
    sort(nd+1,nd+q+1);
    
    int l=1,r=0;
    for(int i=1;i<=q;i++){
        while(l<nd[i].l) update1(l),l++;
        while(r>nd[i].r) update1(r),r--;
        while(l>nd[i].l) update2(l-1),l--;
        while(r<nd[i].r) update2(r+1),r++;
        nd[i].ans=calc;
    }
    sort(nd+1,nd+q+1,cmp);
    for(int i=1;i<=q;i++) printf("%d\n",nd[i].ans); 
}
int main(){
    init();
    
    return 0; 
}
Last modification:February 15th, 2019 at 09:42 pm

Leave a Comment