#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<double, double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=350003;
const int mxM=1010;
const int mxK=105;
const int MOD=1000000007;
const ll INF=1e18;
const ll P1=1000000007;
const ll P2=1000000009;
typedef struct query{
int s, e, idx;
ll ans;
}query;
int N, M, Q, L;
int A[mxN];
query T[mxN];
int ncnt[mxN]; ///number
int tcnt[mxN]; ///type
int bag[mxN];
int typ_cnt;
int ns=1, ne;
int maxi;
bool used;
unordered_map <int, int> s;
ll ans;
ll lval, rval;
int nsum;
bool cmp1(query a, query b)
{
if(a.s/M!=b.s/M) return a.s<b.s;
return a.e<b.e;
}
void set_remove(int now)
{
tcnt[now]--;
if(s[now]==1)
{
s.erase(now);
bag[now/M]--;
}
else s[now]--;
}
void set_insert(int now)
{
tcnt[now]++;
if(!s.count(now)) s[now]=1, bag[now/M]++;
else s[now]++;
}
void mo(int pos, int typ)
{
int pre=ncnt[A[pos]], now=ncnt[A[pos]]+typ;
ncnt[A[pos]]+=typ;
if(pre==0) typ_cnt++;
if(now==0) typ_cnt--;
if(pre!=0) set_remove(pre);
if(now!=0) set_insert(now);
}
ll sum(ll a, ll d, ll n)
{
return (a*(a+1)*n+(2*a+1)*d*n*(n-1)/2+d*d*(n-1)*n*(2*n-1)/6)/2;
}
void typ_insert(int now, int num)
{
if(now==maxi && !used)
{
used=true;
num--;
}
if(num==0) return;
if(lval>rval) swap(lval, rval);
int lcnt=0, rcnt=0;
lcnt+=min((ll)num, (rval-lval)/now);
num-=lcnt;
if(num%2==0) lcnt+=num/2, rcnt+=num/2;
else lcnt+=num/2+1, rcnt+=num/2;
ans-=sum(lval+now, now, lcnt);
ans-=sum(L-lval-lcnt*now, now, lcnt);
lval+=lcnt*now;
ans-=sum(rval+now, now, rcnt);
ans-=sum(L-rval-rcnt*now, now, rcnt);
rval+=rcnt*now;
}
void print()
{
for(int i=1;i<=M;i++) printf("cnt[%d]=%d\n", i, tcnt[i]);
for(auto iter=s.begin();iter!=s.end();iter++) printf("%d ", *iter);
printf("\n");
}
int main()
{
gibon
cin >> N >> Q;
M=min(N, (int)sqrt(N));
for(int i=1;i<=N;i++) cin >> A[i];
for(int i=0;i<Q;i++)
{
cin >> T[i].s >> T[i].e;
T[i].idx=i;
}
sort(T, T+Q, cmp1);
for(int i=0;i<Q;i++)
{
while(ne<T[i].e)
{
ne++;
mo(ne, 1);
}
while(ns>T[i].s)
{
ns--;
mo(ns, 1);
}
while(ne>T[i].e)
{
mo(ne, -1);
ne--;
}
while(ns<T[i].s)
{
mo(ns, -1);
ns++;
}
for(int i=N/M;i>=0;i--) if(bag[i]!=0)
{
for(int j=i*M+M-1;j>=i*M;j--) if(tcnt[j]!=0)
{
maxi=j;
break;
}
break;
}
used=false;
L=T[i].e-T[i].s+1;
ans=(ll)L*(L+1)/2*typ_cnt;
lval=0, rval=0;
for(auto ele : s)
{
typ_insert(ele.fir, ele.sec);
}
T[i].ans=ans;
}
sort(T, T+Q, [](query a, query b){return a.idx<b.idx;});
for(int i=0;i<Q;i++) cout << T[i].ans << '\n';
}
Compilation message
diversity.cpp: In function 'void print()':
diversity.cpp:98:62: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::pair<const int, int>' [-Wformat=]
98 | for(auto iter=s.begin();iter!=s.end();iter++) printf("%d ", *iter);
| ~^ ~~~~~
| | |
| int std::pair<const int, int>
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
