2023年牛客多校第五场A

清初 / 2023-08-05 / 原文

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();
	}
}