nbut 1457 Sona

https://ac.2333.moe/Problem/view.xhtml?id=1457 题意：求一段区间内数字个数的立方和。思路：由于一共才1E5,而数字1E9,所以先离散化，再莫队，类似小z的袜子。注意：%lld会WA,要用%I64d
  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年02月17日 星期三 16时11分00秒
  4File Name :code/nbut/1457.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=1E5+7;
 34int a[N],b[N];
 35LL  cnt[N];
 36int pos[N];
 37LL ans[N];
 38LL sum;
 39int n,m;
 40
 41struct node
 42{
 43    int l,r;
 44    int id;
 45
 46    bool operator < (node b)const
 47    {
 48	if (pos[l]==pos[b.l]) return r<b.r;
 49	return pos[l]<pos[b.l];
 50    }
 51}q[N];
 52
 53
 54
 55void update(int x,int d)
 56{
 57
 58	sum-=cnt[a[x]]*cnt[a[x]]*cnt[a[x]];
 59	cnt[a[x]]+=d;
 60	sum +=cnt[a[x]]*cnt[a[x]]*cnt[a[x]];
 61
 62}
 63int main()
 64{
 65	#ifndef  ONLINE_JUDGE
 66	freopen("code/in.txt","r",stdin);
 67  #endif
 68
 69	while (scanf("%d",&n)!=EOF)
 70	{
 71	    ms(cnt,0);
 72	    ms(ans,0);
 73	    sum = 0LL;
 74
 75	    int siz = 330;//sqrt(100000);
 76	    for ( int i = 1 ; i <= n ; i++)
 77	    {
 78		scanf("%d",&b[i]);
 79		pos[i] = (i-1)/siz;
 80		a[i] = b[i];
 81	    }
 82
 83	    sort(b+1,b+n+1);  //离散化
 84	    int t = unique(b+1,b+n+1)-b-1;
 85	    for ( int i = 1 ; i <= n ; i++) a[i]=lower_bound(b+1,b+t+1,a[i])-b;
 86
 87	    scanf("%d",&m);
 88	    for ( int i = 1 ; i <= m ; i++)
 89	    {
 90		scanf("%d %d",&q[i].l,&q[i].r);
 91		q[i].id = i ;
 92	    }
 93	    sort(q+1,q+m+1);
 94
 95	    int pl=1,pr=0;
 96	    int id,l,r;
 97	    for ( int i = 1 ; i <= m ; i++)
 98	    {
 99		id = q[i].id;
100		r = q[i].r;
101		l = q[i].l;
102
103		if (pr<r)
104		{
105		    for ( int j = pr +1 ; j <= r ; j++) update(j,1);
106		}
107		else
108		{
109		    for (int j = r+1 ; j <= pr ; j++) update(j,-1);
110		}
111		pr = r;
112
113		if (l<pl)
114		{
115		    for ( int j = l ; j <= pl-1 ; j++) update(j,1);
116		}
117		else
118		{
119		    for (int j = pl ; j <= l-1 ; j++) update(j,-1);
120		}
121		pl = l;
122
123		ans[id] = sum;
124	    }
125
126	    for ( int i = 1 ; i <= m ; i++) printf("%I64d\n",ans[i]); //用%lld会WA...也不给个警告
127	}
128
129  #ifndef ONLINE_JUDGE
130  fclose(stdin);
131  #endif
132    return 0;
133}
相关文章
