普通莫队
前言
莫队算法可谓是充满暴力啊哈哈哈哈哈哈
因为莫队更深层次的内容关联到个人目前还没啃的东西，所以先跳过
D-query - SPOJ - DQUERY
题意
对于q次询问，给出每个询问区间内去重后的元素个数
思路
莫队模板题
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 1e6 + 15;
struct node{
int l, r, id;
};
int a[N];
int ans[N];
int cnt[N];
node que[N];
int block_size;
bool cmp(const node& a, const node& b){
if(a.l/block_size == b.l/block_size){
return a.r < b.r;
}else{
return a.l/block_size < b.l/block_size;
}
}
inline void add(const int& pos, int& answer){
cnt[a[pos]]++;
if(cnt[a[pos]] == 1){
answer++;
}
}
inline void del(const int& pos, int& answer){
cnt[a[pos]]--;
if(cnt[a[pos]] == 0){
answer--;
}
}
int main(){
int n;
while(~scanf("%d", &n)){
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < n; i++) { scanf("%d", &a[i]); }
block_size = (int)sqrt(n);
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++){
scanf("%d%d", &que[i].l, &que[i].r);
que[i].l--;
que[i].r--;
que[i].id = i;
}
sort(que, que + q, cmp);
int l = 0, r = -1;
int answer = 0;
for(int i = 0; i < q; i++){
while(que[i].l < l) { add(--l, answer); }
while(l < que[i].l) { del(l++, answer); }
while(que[i].r < r) { del(r--, answer); }
while(r < que[i].r) { add(++r, answer); }
ans[que[i].id] = answer;
}
for(int i = 0; i < q; i++){
printf("%d\n", ans[i]);
}
}
}
Powerful array - CodeForces - 86D
题意
对于q次询问，计算询问区间中的 sigma(a[i]*(cnt(a[i])^2))
思路
仍然是一道模板题
（注意本题不要处处long long， 会TLE的）
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 2e5 + 15;
struct node{
int l, r, id;
};
int a[N];
ll ans[N];
int cnt[N*5];
node que[N];
int unit;
ll answer;
bool cmp(node& a, node& b){
if(a.l/unit == b.l/unit) return a.r < b.r;
else return a.l/unit < b.l/unit;
}
void add(int pos){
answer += (ll)a[pos] * (cnt[a[pos]] << 1 | 1); // (a+1)^2 - a^2 = 2 * a + 1
cnt[a[pos]]++;
}
void del(int pos){
answer -= (ll)a[pos] * ((cnt[a[pos]] << 1) - 1); // (a-1)^2 - a^2 = -2*a + 1 = -(2*a - 1)
cnt[a[pos]]--;
}
int main(){
int n, q;
scanf("%d%d", &n, &q);
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < n; i++) { scanf("%d", &a[i]); }
unit = sqrt(n);
for(int i = 0; i < q; i++){
scanf("%d%d", &que[i].l, &que[i].r);
que[i].l--;
que[i].r--;
que[i].id = i;
}
sort(que, que + q, cmp);
int l = que[0].l;
int r = que[0].l - 1;
answer = 0;
for(int i = 0; i < q; i++){
while(que[i].l < l) { add(--l); }
while(l < que[i].l) { del(l++); }
while(que[i].r < r) { del(r--); }
while(r < que[i].r) { add(++r); }
ans[que[i].id] = answer;
}
for(int i = 0; i < q; i++){
printf("%I64d\n", ans[i]);
}
}
