【BZOJ1878】HH的项链

1878: [SDOI2009]HH的项链

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 3907  Solved: 1955
[Submit][Status][Discuss]

Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此， 他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同 的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解 决这个问题。

Input

第一行：一个整数N，表示项链的长度。 第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。 第三行：一个整数M，表示HH询问的个数。 接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

Output

M行，每行一个整数，依次表示询问对应的答案。

Sample Input

6
1 2 3 4 3 5
3
1 2
3 5
2 6

Sample Output

2
2
4

HINT


对于20%的数据，N ≤ 100，M ≤ 1000；
对于40%的数据，N ≤ 3000，M ≤ 200000；
对于100%的数据，N ≤ 50000，M ≤ 200000。

Source

Day2

sol

莫队练手题

可以可持久化线段树 直接统计答案 复杂度nlogn

但是我懒得写了怎么办= =

/*To The End Of The Galaxy*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include<set>
#include
#include
#define debug(x) cerr<<#x<<"="<#define INF 0x7f7f7f7f
#define llINF 0x7fffffffffffll
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
inline int init()
{
    int now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
inline long long llinit()
{
    long long now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
#define pos(i) ((i-1)/block)+1
struct node
{
    int l,r,id,ans;
}query[200005];
int block;
int f[1000005];
int n,q;
int a[1000005];
bool cmp(node a,node b)
{
    if(pos(a.l)!=pos(b.l))
    {
        return a.l<b.l;
    }
    else return a.r<b.r;
}
bool idcmp(node a,node b)
{
    return a.id<b.id;
}
int ans=0;
void add(int now)
{
    if(f[a[now]]==0)ans++;
    f[a[now]]++;
}
void del(int now)
{
    if(f[a[now]]-1==0)ans--;
    f[a[now]]--;
}
int main()
{
    n=init();
    for(int i=1;i<=n;i++)
    {
        a[i]=init();
    }
    q=init();
    block=sqrt(q);
    for(int i=1;i<=q;i++)
    {
        query[i].l=init();query[i].r=init();query[i].id=i;
    }
    sort(query+1,query+1+q,cmp);
    int l=1,r=0;
    for(int i=1;i<=q;i++)
    {
        if(query[i].r>r)
        {
            for(r=r+1;r<=query[i].r;r++)//queryi.r要加上 
            {
                add(r);
            }
        }
        else if(r>query[i].r)
        {
            for(;r>query[i].r;r--)//queryi.r不能删 
            {
                del(r);
            }
        }
        if(l<query[i].l)
        {
            for(;l//queryi.l不能删 
            {
                del(l);
            }
        }
        else if(l>query[i].l)
        {
            for(l=l-1;l>=query[i].l;l--)//query[i].l要加上 
            {
                add(l);
            }
        }
        r=query[i].r;l=query[i].l;
        query[i].ans=ans;
    }
    sort(query+1,query+1+q,idcmp);
    for(int i=1;i<=q;i++)
    {
        printf("%d\n",query[i].ans);
    }
    return 0;
}
数据结构-主席树莫队可持久化线段树

相关

【莫队算法】

莫队算法小记

可持久化线段树

P4688-[Ynoi2016]掉进兔子洞【莫队,bitset】

【CodeForces】700 D. Huffman Coding on Segment 哈夫曼树+莫队+分块

二次离线莫队学习笔记

【YBT2022寒假Day5 A】序列计数（组合数）（莫队）

【洛谷 P3674】 小清新人渣的本愿（bitset，莫队）

[后缀数组][二分][莫队]luogu P2336 [SCOI2012]喵星球上的点名

待修改的莫队 洛谷P1903 [国家集训队] 数颜色 / 维护队列

二次离线莫队学习笔记

P3919 【模板】可持久化线段树 1（可持久化数组） 线段树扩展

标签