#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
int n,q,k;
const int maxN = 3e5+10;
bool cmp(pair<pii,int> a, pair<pii,int> b){
if((a.ff.ff / k) == (b.ff.ff / k)) return a.ff.ss < b.ff.ss;
return (a.ff.ff / k) < (b.ff.ff / k);
}
multiset<int> s;
int times[maxN];
signed main(){
cin >> n >> q;
k = n / sqrt(q);
int arr[n];
F(n) cin >> arr[i];
pair<pii, int> queries[q];
F(q){
int l,r;
cin >> l >> r;
l--; r--;
queries[i] = mp(mp(l, r), i);
}
sort(queries, queries + q, cmp);
int fin[q];
if(q == 1){
int times[maxN] = {};
F(n) times[arr[i]]++;
sort(times, times+maxN);
int ans = (n * (n+1)) / 2;
int ldist = 0;
int rdist = 0;
F(maxN - 1){
if(times[i] == 0) continue;
if(ldist > rdist) swap(ldist, rdist);
ldist += times[i];
ans += (n - ldist) * ldist;
}
printf("%lld\n", ans);
}else{
int cl = 0; int cr = -1;
F(q){
int nl = queries[i].ff.ff; int nr = queries[i].ff.ss;
int id = queries[i].ss;
// process the right bound change
if(nr > cr){
while(nr > cr){
cr++;
if(times[arr[cr]] != 0)
s.erase(s.lower_bound(times[arr[cr]]));
times[arr[cr]]++;
s.insert(times[arr[cr]]);
}
}else if(nr < cr){
while(nr < cr){
s.erase(s.lower_bound(times[arr[cr]]));
times[arr[cr]] --;
if(times[arr[cr]] != 0){
s.insert(times[arr[cr]]);
}
cr--;
}
}
// process the left bound change
if(nl > cl){
while(nl > cl){
s.erase(s.lower_bound(times[arr[cl]]));
times[arr[cl]]--;
if(times[arr[cl]] != 0){
s.insert(times[arr[cl]]);
}
cl++;
}
}else if(nl < cl){
while(nl < cl){
cl--;
if(times[arr[cl]] != 0){
s.erase(s.lower_bound(times[arr[cl]]));
}
times[arr[cl]]++;
s.insert(times[arr[cl]]);
}
}
// answer the query
int ans = (cr-cl+1) * (cr-cl+2) / 2;
int ldist = 0, rdist = 0;
auto it = s.begin();
F((int) s.size() - 1){
if(ldist > rdist) swap(ldist, rdist);
ldist += *it;
ans += ((cr-cl+1) - ldist) * ldist;
}
fin[id] = ans;
}
}
F(q){
printf("%lld\n", fin[i]);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
