1：题目链接
https://ac.nowcoder.com/acm/contest/57359/A
题意：
给你一个数组，让你找出区间l,r之间满足 l ≤ i < j < k ≤ r, ai = ak > aj 的个数
思路
1:我们先找出当前位置x小于x的数有多少个
例如：9 8 5 4 5 1 5 1 5 8
对应：0 0 0 0 1 0 2 0 3 7
你会发现假如有i,k,j满足，则个数为c[k]-c[i]；
这一部分通过树状数组实现
2：找区间满足，通过莫队，其实就是莫队的板子
代码：
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e6,md = 1e9+7,B = 700;
struct NOW{
int l;
int r;
int site;
}edge[N];
int a[N],ans[N],cnt[N],sum,pan[N];
int n,m,x;
int b[N],c[N];
bool cmp(NOW w,NOW s)
{
int xx = w.l/B,yy = s.l/B;
if(xx != yy)
return xx < yy;
else
{
if(xx%2)
return w.r < s.r;
else
return w.r > s.r;
}
}
void add(int u)
{
sum += abs(pan[a[u]] - cnt[a[u]]*b[u]);//当前加入的
cnt[a[u]]++;//计算看是否重复出现
pan[a[u]]+=b[u];
}
void sub(int u)
{
sum -= abs(pan[a[u]] - cnt[a[u]]*b[u]);
cnt[a[u]]--;
pan[a[u]]-=b[u];
}
void modify(int x)
{
for(;x<=N;)
{
c[x]++;
x += (x&-x);
}
}
int query(int x)
{
int res = 0;
for(;x;)
{
res += c[x];
x-= (x&-x);
}
return res;
}
void solve()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)//找前面有多少个小于当前的数
{
cin >> a[i];
b[i] = query(a[i]-1);
modify(a[i]);
}
for(int i = 1;i <= m;i ++)
{
int l,r;
cin >> l >> r;
edge[i] = {l,r,i};
}
sort(edge+1,edge+m+1,cmp);//莫队
int res = 0,pos = 1;
for(int i = 1;i <= m;i ++)
{
while(res < edge[i].r) res++,add(res);
while(res > edge[i].r) sub(res),res--;
while(pos < edge[i].l) sub(pos),pos++;
while(pos > edge[i].l) pos--,add(pos);
ans[edge[i].site] = sum;
}
for(int i = 1;i <= m;i ++)
{
cout << ans[i] << '\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
while(t--)
{
solve();
}
}