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}