cogs 1619. [HEOI2012]采花 AC

1619. [HEOI2012]采花

★★☆ 输入文件：1flower.in 输出文件：1flower.out 简单对比
时间限制：5 s 内存限制：128 MB

【题目描述】

萧薰儿是古国的公主，平时的一大爱好是采花。

今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。花园足够大，容纳了n朵花，花有c种颜色（用整数1-c表示），且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了m个行程，然后一一向你询问公主能采到多少朵花（她知道你是编程高手，定能快速给出答案！），最后会选择令公主最高兴的行程（为了拿到更多奖金！）。

【输入格式】

第一行四个空格隔开的整数n、c以及m。接下来一行n个空格隔开的整数，每个数在[1, c]间，第i个数表示第i朵花的颜色。接下来m行每行两个空格隔开的整数l和r（l ≤ r），表示女仆安排的行程为公主经过第l到第r朵花进行采花。

【输出格式】

共m行，每行一个整数，第i个数表示公主在女仆的第i个行程中能采到的花的颜色数。

【样例输入】

【样例输出】

2 
  0 0 1 0 
  【样例说明】
  询问[1, 5]：公主采颜色为1和2的花，由于颜色3的花只有一朵，公主不采；询问[1, 2]：颜色1和颜色2的花均只有一朵，公主不采；
  询问[2, 2]：颜色2的花只有一朵，公主不采；
  询问[2, 3]：由于颜色2的花有两朵，公主采颜色2的花；
  询问[3, 5]：颜色1、2、3的花各一朵，公主不采。

【提示】

【数据范围】

对于100%的数据，1 ≤ n ≤ 10^6，c ≤ n，m ≤10^6。

考试时20分代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<string>
 7  
 8 using namespace std;
 9 const int N=1000010;
10  
11 int a[N];
12 int b[N];
13  
14 inline int read()
15 {
16     int x=0,f=1;
17     char c=getchar();
18     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
19     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
20     return x*f;
21 }
22  
23 int main()
24 {
25     freopen("1flower.in","r",stdin);
26     freopen("1flower.out","w",stdout);
27     int n=read();
28     int m=read();
29     int k=read();
30     for(int i=1;i<=n;i++)
31         a[i]=read();
32     for(int i=1;i<=k;i++)
33     {
34         int u=read();
35         int v=read();
36         int Answer=0;
37         if(u==v){printf("0
");continue ;}
38         memset(b,0,sizeof(b));
39         int maxn=-1;
40         
41         for(int j=u;j<=v;j++)
42         {
43             b[a[j]]++;
44             maxn=max(maxn,a[j]);
45         }
46         
47         for(int j=1;j<=maxn;j++)
48             if(b[j]>=2)
49                 Answer++;
50                 
51         printf("%d
",Answer);
52     }
53     
54     return 0;
55 }
56

显然，这是一道莫队题，然而莫队在cogs上只得70分：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
 
using namespace std;
const int N=2000010;

int a[N],number[N],answer[N],pos[N];
int n,col,m,base,ans;
struct node{
    int l,r,id;
}E[N];

inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}

inline bool cmp(node a,node b)
{
    if(pos[a.l]==pos[b.l])
        return a.r<b.r;
    else
        return a.l<b.l;
}

void add(int x)
{
    number[x]++;
    if(number[x]==2)
        ans++;
}

void dale(int x)
{
    number[x]--;
    if(number[x]==1)
        ans--;
}

inline void modui()
{
    int ll=1,rr=0;
    for(int i=1;i<=m;i++)
    {
        for(;E[i].l<ll;ll--)add(a[ll-1]);
        for(;E[i].l>ll;ll++)dale(a[ll]);
        for(;E[i].r<rr;rr--)dale(a[rr]);
        for(;E[i].r>rr;rr++)add(a[rr+1]);
        answer[E[i].id]=ans;
    }
}

int main()
{
    freopen("1flower.in","r",stdin);
    freopen("1flower.out","w",stdout);
    n=read(),col=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=m;i++)
        E[i].l=read(),
        E[i].r=read(),
        E[i].id=i;
    base=sqrt(n);
    for(int i=1;i<=n;i++)
        pos[i]=(i-1)/base+1;
    sort(E+1,E+m+1,cmp);
    modui();
    for(int i=1;i<=m;i++)
        printf("%d
",answer[i]);
    return 0;
}
/*
5  3  5
1  2  2  3  1
1  5
1  2
2  2
2  3
3  5
2
0
0
1
0
*/

莫队+几个inline就可以过的：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
 
using namespace std;
const int N=2000010;
 
int a[N],number[N],answer[N],pos[N];
int n,col,m,base,ans;
struct node{
    int l,r,id;
}E[N];
 
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
 
inline bool cmp(node a,node b)
{
    if(pos[a.l]==pos[b.l])
        return a.r<b.r;
    else
        return a.l<b.l;
}
 
inline void add(int x)
{
    number[x]++;
    if(number[x]==2)
        ans++;
}
 
inline void dale(int x)
{
    number[x]--;
    if(number[x]==1)
        ans--;
}
 
inline void modui()
{
    int ll=1,rr=0;
    for(int i=1;i<=m;i++)
    {
        for(;E[i].l<ll;--ll)add(a[ll-1]);
        for(;E[i].l>ll;++ll)dale(a[ll]);
        for(;E[i].r<rr;--rr)dale(a[rr]);
        for(;E[i].r>rr;++rr)add(a[rr+1]);
        answer[E[i].id]=ans;
    }
}
 
int main()
{
    freopen("1flower.in","r",stdin);
    freopen("1flower.out","w",stdout);
    n=read(),col=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    base=sqrt(n);
    for(int i=1;i<=n;i++)
        pos[i]=(i-1)/base+1;
        
    for(int i=1;i<=m;i++)
        E[i].l=read(),
        E[i].r=read(),
        E[i].id=i;
    sort(E+1,E+m+1,cmp);
    modui();
    for(int i=1;i<=m;i++)
        printf("%d
",answer[i]);
    return 0;
}

然而对于这个树状数组我并没有看懂：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <list>
#include <cmath>
using namespace std;
#define F1 "1flower.in"
#define F2 "1flower.out"
#define MAXN 1000002
int pre[MAXN];
int last[MAXN];
int data[MAXN];
int cnt[MAXN];
int ans[MAXN];
struct que
{
    int l, r;
    int id;
}ques[MAXN];
#define Q(i) ques[i]
bool cmp(const que &a, const que &b)
{
   return a.r < b.r;
}
int n, c, m;
void add(int x, int v)
{
    for(int i = x; i <= n; i += i&-i)
        cnt[i] += v;
}
int get_s(int x)
{
    int s = 0;
    for(int i = x; i > 0; i -= i&-i)
        s += cnt[i];
    return s;
}
int main()
{
    freopen(F1, "r", stdin);
    freopen(F2, "w", stdout);
    scanf("%d %d %d", &n, &c, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", data+i);
        pre[i] = last[data[i]];
        last[data[i]] = i;
    }
    for(int i =  0; i < m; i++)
    {
        que &q = ques[i];
        scanf("%d %d", &q.l, &q.r);
        q.id = i;
    }
    sort(ques, ques+m, cmp);
    int t = 0;
    for(int i = 1; i <= n; i++)
    {
        if(pre[i])
        {
            add(pre[i]+1, -1);
            add(pre[pre[i]]+1, 1);
        }
        while(i == ques[t].r)
        {
            ans[ques[t].id] = get_s(ques[t].l);
            t++;
        }
    }
    for(int i = 0; i < m; i++)
        printf("%d ", ans[i]);
    return 0;
}

然而树状数组<1000;莫队4000++