nbut 1457 Sona

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E5+7;
 7int a[N],b[N];
 8LL  cnt[N];
 9int pos[N];
10LL ans[N];
11LL sum;
12int n,m;

1struct node
2{
3    int l,r;
4    int id;

1    bool operator < (node b)const
2    {
3	if (pos[l]==pos[b.l]) return r<b.r;
4	return pos[l]<pos[b.l];
5    }
6}q[N];

1	sum-=cnt[a[x]]*cnt[a[x]]*cnt[a[x]];
2	cnt[a[x]]+=d;
3	sum +=cnt[a[x]]*cnt[a[x]]*cnt[a[x]];

1}
2int main()
3{
4	#ifndef  ONLINE_JUDGE 
5	freopen("code/in.txt","r",stdin);
6  #endif

1	while (scanf("%d",&n)!=EOF)
2	{
3	    ms(cnt,0);
4	    ms(ans,0);
5	    sum = 0LL;

1	    int siz = 330;//sqrt(100000);
2	    for ( int i = 1 ; i <= n ; i++)
3	    {
4		scanf("%d",&b[i]);
5		pos[i] = (i-1)/siz;
6		a[i] = b[i];
7	    }

1	    sort(b+1,b+n+1);  //离散化
2	    int t = unique(b+1,b+n+1)-b-1;
3	    for ( int i = 1 ; i <= n ; i++) a[i]=lower_bound(b+1,b+t+1,a[i])-b;

1	    scanf("%d",&m);
2	    for ( int i = 1 ; i <= m ; i++)
3	    {
4		scanf("%d %d",&q[i].l,&q[i].r);
5		q[i].id = i ;
6	    }
7	    sort(q+1,q+m+1);

1	    int pl=1,pr=0;
2	    int id,l,r;
3	    for ( int i = 1 ; i <= m ; i++)
4	    {
5		id = q[i].id;
6		r = q[i].r;
7		l = q[i].l;

1		if (pr<r)
2		{
3		    for ( int j = pr +1 ; j <= r ; j++) update(j,1);
4		}
5		else
6		{
7		    for (int j = r+1 ; j <= pr ; j++) update(j,-1);
8		}
9		pr = r;

1		if (l<pl)
2		{
3		    for ( int j = l ; j <= pl-1 ; j++) update(j,1);
4		}
5		else
6		{
7		    for (int j = pl ; j <= l-1 ; j++) update(j,-1);
8		}
9		pl = l;

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}