#include <bits/stdc++.h>
using namespace std;
template <typename T>
class FenwickTree{
public:
T* FT;
int n;
bool negmode;
FenwickTree(int sz = 300000, bool negindex = true){
n = sz+505;
FT = new T[n];
fill(FT, FT+n, (T)0);
negmode = negindex;
}
inline void add(int idx, T amt){
if(negmode) idx += n/2;
while(idx < n){
FT[idx] += amt;
idx += idx & -idx;
}
}
inline T sum(int idx){
if(negmode) idx += n/2;
T ret = (T)0;
while(idx > 0){
ret += FT[idx];
idx -= idx & -idx;
}
return ret;
}
inline int lower_bound(const int& v){
if(v > FT[1]) return 0;
int cur = 1 << 18;
int part = FT[cur];
for(int i = 17; i >= 0; i--){
if(part >= v){
cur += 1 << i;
part += FT[cur];
}else{
part -= FT[cur];
cur -= 1 << i;
part += FT[cur];
}
}
if(part < v) return cur-1;
return cur;
}
inline int upper_bound(const int& v){
return lower_bound(v+1);
}
};
FenwickTree<int> FT1; // Ri
FenwickTree<long long> FT2; // Ri * i
int cnt[300005];
int a[300005];
// abstract deque
// fenwick indexing:
// [...] [-3] [-2] [-1] [0] [1] [2] [...]
// deque indexing:
// [...] [6] [4] [2] [1] [3] [5] [...]
// invariant:
// dq[-i] <= dq[i] for all positive i
// dq[-i] >= dq[i+1] for all positive i
inline int dq2fw(int idx){
return idx/2 * (idx % 2 ? 1 : -1);
}
FenwickTree<int> dq(300000, false); // using deque indexing
inline long long deque_add(const int& x){
int idx = dq.upper_bound(x)+1;
dq.add(idx, 1);
dq.add(idx+1, -1);
int b = dq2fw(idx);
FT1.add(b, 1);
FT2.add(b, b);
return FT2.sum(FT2.n/2-1) - FT2.sum(b) - 1ll * (b-1) * (FT1.sum(FT1.n/2-1) - FT1.sum(b))
+ 1ll * (b+1) * FT1.sum(b-1) - FT2.sum(b-1) + x+1;
}
inline long long deque_remove(const int& x){
int idx = dq.lower_bound(x);
dq.add(idx, -1);
dq.add(idx+1, 1);
int b = dq2fw(idx);
FT1.add(b, -1);
FT2.add(b, -b);
return FT2.sum(FT2.n/2-1) - FT2.sum(b) - 1ll * (b-1) * (FT1.sum(FT1.n/2-1) - FT1.sum(b))
+ 1ll * (b+1) * FT1.sum(b-1) - FT2.sum(b-1) + x;
}
vector<tuple<int,int,int>> qbckt[2048]; // (L, R, Q)
long long answer[50005];
int qcnt[2048];
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; i++){
scanf("%d",a+i);
}
int SQRT = 1300;
vector<pair<int,int>> rawq;
for(int i = 0; i < q; i++){
int l, r;
scanf("%d%d",&l,&r);
rawq.emplace_back(l,r);
qcnt[l/SQRT]++;
}
for(int i = 0; i <= n/SQRT+2; i++){
qbckt[i].reserve(qcnt[i]);
}
for(int i = 0; i < q; i++){
tie(l, r) = rawq[i];
qbckt[l / SQRT].emplace_back(l, r, i);
}
int lptr = 1;
int rptr = 0;
long long ans = 0ll;
for(int i = 0; i <= n/SQRT+2; i++){
sort(qbckt[i].begin(), qbckt[i].end(), [](tuple<int,int,int> x, tuple<int,int,int> y){
return get<1>(x) < get<1>(y);
});
// Below goes declaratively.
for(auto qr : qbckt[i]){
int l, r, qnum;
tie(l, r, qnum) = qr;
while(rptr < r){
rptr++;
ans += deque_add(cnt[a[rptr]]);
cnt[a[rptr]]++;
}
while(lptr > l){
lptr--;
ans += deque_add(cnt[a[lptr]]);
cnt[a[lptr]]++;
}
while(lptr < l){
ans -= deque_remove(cnt[a[lptr]]);
cnt[a[lptr]]--;
lptr++;
}
while(rptr > r){
ans -= deque_remove(cnt[a[rptr]]);
cnt[a[rptr]]--;
rptr--;
}
answer[qnum] = ans;
}
}
for(int i = 0; i < q; i++){
printf("%lld\n", answer[i]);
}
return 0;
}
Compilation message
diversity.cpp: In function 'int main()':
diversity.cpp:115:9: error: 'l' was not declared in this scope
115 | tie(l, r) = rawq[i];
| ^
diversity.cpp:115:12: error: 'r' was not declared in this scope
115 | tie(l, r) = rawq[i];
| ^
diversity.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d%d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~
diversity.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d",a+i);
| ~~~~~^~~~~~~~~~
diversity.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | scanf("%d%d",&l,&r);
| ~~~~~^~~~~~~~~~~~~~
