The 2022 ICPC Asia Kunming Regional Programming Contest_Easy Str
//
// https://ac.nowcoder.com/acm/contest/32708/E
#include "stdafx.h"
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1E5 + 100;
int n, m, block;
int arr[N]={
0,1, 2, 3,4, 1,2,3
};
/* 莫队算法 (Mo's Algorithm)
For query 4.4, repeat=3
123.....
....123
1...23
12....3
For query 3.3. repeat=2
12....3
1...23
....123
*/
long long res[N];
pair<int, int> cnt[N];
struct Mo {
int L, r, idx;
bool operator < (const Mo &rhs) const {
if (L / block == rhs.L / block) {
return r < rhs.r;
}
return L / block < rhs.L / block;
}
};
Mo qry[N];
int Q[N][2]={
1, 1,
3, 3,
2 ,3,
2 ,4,
1 ,3,
1 ,4,
4,4
};
int main() {
n=7;m=7;
/*
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}*
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> qry[i].l >> qry[i].r;
qry[i].i = i;
}*/
for (int i = 1; i <= m; i++) {
qry[i].L =Q[i-1][0]; qry[i].r=Q[i-1][1];
qry[i].idx = i;
}
block = sqrt(n);
cout<<block<<endl;
sort(qry + 1, qry + 1 + m);
for (int i = 1; i <= m; i++) cout<<qry[i].idx<<" ";
cout<<endl;
int left = 1, r = n;
for (int i = 1; i <= n; i++) {
cout<<cnt[arr[i]].first<<", sec="<<cnt[arr[i]].second <<endl;
}
int repeat = 0;
for (int i = 1; i <= m; i++) {
while (left < qry[i].L ) {
repeat += cnt[arr[left]].second;
cnt[arr[left++]].first += 1;
}
cout <<" repeat="<<repeat<<" i="<<i<<" left="<<left<<" r="<<r<<endl;
while (left > qry[i].L ) {
cnt[arr[--left]].first -= 1;
repeat -= cnt[arr[left]].second;
}
cout <<" repeat="<<repeat<<" i="<<i<<" left="<<left<<" r="<<r<<endl;
while (r < qry[i].r) {
cnt[arr[++r]].second -= 1;
repeat -= cnt[arr[r]].first;
}
cout <<" repeat="<<repeat<<" i="<<i<<" left="<<left<<" r="<<r<<endl;
while (r > qry[i].r) {
repeat += cnt[arr[r]].first;
cnt[arr[r--]].second += 1;
}
cout <<" repeat="<<repeat<<" i="<<i<<" left="<<left<<" r="<<r<<endl;
cout <<repeat<<" i="<<i<<" r="<<r<<" L="<<qry[i].L<<" qry[i].r="<<qry[i].r<<" qry[i].idx= "<<qry[i].idx<<endl;
for (int ii = 1; ii <= n; ii++)
{
cout<<cnt[arr[ii]].first<<", sec="<<cnt[arr[ii]].second <<endl;
}
res[qry[i].idx] = 1LL * qry[i].L * (n - qry[i].r + 1) - repeat;
cout<<res[qry[i].idx]<<"=res[qry[i].idx]"<<endl;
}
for (int i = 1; i <= m; i++) {
cout << res[i] << endl;
}
return 0;
}
