题意查询给定[L, R]区间内 逆序对数 ==k的子区间的个数。
我们只需要求出 子区间小于等于k的个数和小于等于k-1的个数，然后相减就得出答案了。
对于i(1≤i≤n)，我们计算ri表示[i,ri]的逆序对数小于等于K，且ri的值最大。（ri对应代码中的cnt数组）
显然ri单调不降，我们可以通过用两个指针扫一遍，利用树状数组计算出r数组。
对于每个询问L,R，我们要计算的是∑i=LR[min(R,ri)−i+1]
由于ri具有单调性，那我们直接在上面二分即可，然后记一个前缀和（s数组）。
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
const int maxn = 1e5+;
int n, q, tot, a[maxn];
ll k, vec[maxn];
int lowbit (int x)
{
return x & -x;
}
ll arr[maxn];
int M ;
void modify(int x, int d)
{
while (x < M)
{
arr[x] += d;
x += lowbit(x);
}
}
ll sum(int x)
{
ll res = ;
while (x)
{
res += arr[x];
x -= lowbit(x);
}
return res;
}
ll cnt[][maxn];
ll s[][maxn];
ll solve (int L, int R, ll x, int w) // 小于等于x的数量
{
if (x < )
return ;
//int tmp = 0;
int tmp = lower_bound(cnt[w]+L, cnt[w]+R+, (ll)R) - cnt[w];
while (tmp >= R+) // cnt数组中所有数都小于 R时，，得到的tmp是大于R+1的
tmp--;
while (cnt[w][tmp] > R && tmp >= L)
tmp--;
if (tmp < L)
return (ll)R*(ll)(R-L+) - (ll)(L+R)*(ll)(R-L+)/;
return s[w][tmp] - s[w][L-] - (ll)(R-tmp)*(ll)(R+tmp+)/+ (ll)(R-tmp)*(ll)R;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt", "w", stdout);
#endif
while (~scanf ("%d%d%I64d", &n, &q, &k))
{
M = n + ;
memset(arr, , sizeof (arr));
memset(cnt, , sizeof (cnt));
memset(s, , sizeof(s));
for (int i = ; i < n; i++)
{
scanf ("%I64d", vec+i);
a[i] = vec[i];
}
sort (vec, vec+n);
tot = unique(vec, vec+n) - vec;
for (int i = ; i < n; i++)
{
a[i] = lower_bound(vec, vec+tot, a[i]) - vec + ; //离散化
}
ll res = ;
//小于等于k
for (int i = , j = ; i < n; i++)
{
for ( ; j < n && res <= k; j++)
{
res += (j - i) - sum(a[j]);
modify(a[j], );
}
if (res >= k)
cnt[][i] = (res > k ? max(,j --): j-) ; // -1是因为 j先加了一下， 才跳出 循环的
else
cnt[][i] = j--;
s[][i] = s[][i-] + cnt[][i] - (i);
modify(a[i], -);
res -= sum(a[i]-);
} //小于等于k-1
res = ;
for (int i = , j = ; i < n; i++)
{
for ( ; j < n && res <= (k-); j++)
{
res += (j-i) - sum(a[j]);
modify(a[j], );
}
if (res >= k-)
cnt[][i] = (res > (k-) ? max(j--,) : j-);
else
cnt[][i] = j--; s[][i] = s[][i-] + cnt[][i] - (i);
modify(a[i], -);
res -= sum(a[i]-);
}
for (int i = ; i < q; i++)
{
int u, v;
scanf ("%d%d", &u, &v);
u--, v--;
if (u > v)
swap(u, v);
ll ans1 = solve(u, v, k, );
ll ans2 = solve(u, v, k-, );
if (k == )
ans1 += (v-u+); // 考虑形如[a, a]的区间
printf("%I64d\n", ans1-ans2 );
}
}
return ;
}