莫队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 5e4+5;
int a[maxn],pos[maxn],cnt[maxn];
long long ans[maxn];
long long res;
struct Q
{
    int l,r,k;
}q[maxn];
bool cmp(Q x,Q y){
		return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l];
}
void Add(int n) { cnt[a[n]]++; res+=cnt[a[n]]*cnt[a[n]]-(cnt[a[n]]-1)*(cnt[a[n]]-1); }
void Sub(int n) { cnt[a[n]]--; res-=(cnt[a[n]]+1)*(cnt[a[n]]+1)-cnt[a[n]]*cnt[a[n]]; }
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    int siz=sqrt(n);
    for(int i=1;i<=n;i++)//注意！！！ 数组是从1开始
    {
        cin>>a[i];
        pos[i]=i/siz;//分块，这也是必要的
    }
    for(int i=0;i<m;i++)
    {
        cin>>q[i].l>>q[i].r;
        q[i].k=i;
    }
    sort(q,q+m,cmp);
    int l=1,r=0;//注意！！！一定要l>r不然会导致结果出错，血的教训！！！！
    for(int i=0;i<m;i++)
    {
        while(q[i].l<l) Add(--l);
        while(q[i].r>r) Add(++r);
        while(q[i].l>l) Sub(l++);
        while(q[i].r<r) Sub(r--);
        ans[q[i].k]=res;
    }
    for(int i=0;i<m;i++)
        cout<<ans[i]<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <iostream>
#include <cstring> 
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
struct node {
	int l,r,k,i;
}; 

node mp[maxn];
int num[maxn];//i出现的次数 
int vis[maxn];//出现i次的数有几个 
int cnt[maxn];//记录答案 
int pos[maxn];
int a[maxn];
int siz=maxn;
bool cmp(node x,node y){
	return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l];
}
void add(int i){
	vis[num[a[i]]]--;
	num[a[i]]++;
	vis[num[a[i]]]++;
}
void sub (int i){

	vis[num[a[i]]]--;
	num[a[i]]--;
	vis[num[a[i]]]++;
}
int main ()
{
	memset (vis,0,sizeof (vis));
	memset (num,0,sizeof (num));
	int n,m;
	cin>>n;
	int siz=sqrt(n); 
	for (int i=1;i<=n;i++){
		cin>>a[i];
		pos[i]=i/siz;
	}
	cin>>m;
	for (int i=1;i<=m;i++){
		cin>>mp[i].l>>mp[i].r>>mp[i].k;
		mp[i].i=i;
	}
	sort (mp+1,mp+1+m,cmp);
	int l=1,r=0;
	for (int i=1;i<=m;i++){
		while (mp[i].l<l) add(--l);
		while (mp[i].r>r) add(++r);
		while (mp[i].l>l) sub(l++);
		while (mp[i].r<r) sub(r--);
		cnt[mp[i].i]=vis[mp[i].k];
	}
	for (int i=1;i<=m;i++){
		cout<<cnt[i]<<endl;
	}
	return 0;
}