赛时 100+75+30+0
A.
求对于区间 \([l, r]\) 的答案，转换成 $ans(R) - ans(L - 1) \(，\)ans(i)$ 表示小于等于 \(i\) 的元素个数。
对于 \(x\)，二分小于等于 \(x\) 的个数，可以直接对于二分的这个数 q 次操作判断，因为如果它可以小于它的一定也可以。时间复杂度 \(O(Q\log n)\)
B.
75pts
设当前的中间的数为 \(now\)，枚举左端点，向右枚举每次相当于插入两个数，如果两个数都大于 \(now\)，那 \(now\) 变为小于它的第一个数，若两个数都小于 \(now\)，那 \(now\) 变成大于它的第一个数，否则就不变，依次更新答案即可，时间复杂度 \(O(n^2 \log n)\)
100pts
枚举中位数，令小于它的数为-1，大于它的数为1，向左向右枚举分别做前缀/后缀和，一个区间满足当且仅当这个区间的和为0，记录一下统计答案即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 7;
int p[N], a[N], f[N], sum1[N], sum2[N];
int sm[N];
int mp[N];
signed main() {
freopen("book.in", "r", stdin);
freopen("book.out", "w", stdout);
int n;
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
a[p[i]] = i;
}
int ans = 0;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= n * 2; j ++) mp[j] = 0;
int now = 0;
sm[a[i]] = 0;
for(int j = a[i] - 1; j >= 1; j --) {
if(p[j] < i) sm[j] = sm[j + 1] - 1;
else sm[j] = sm[j + 1] + 1;
}
for(int j = a[i] + 1; j <= n; j ++) {
if(p[j] < i) sm[j] = sm[j - 1] - 1;
else sm[j] = sm[j - 1] + 1;
}
for(int j = 1; j <= a[i]; j ++) mp[n + sm[j]] += j;
for(int j = a[i]; j <= n; j ++) ans += j * i * mp[n - sm[j]];
}
cout << ans << endl;
}