HDU 6058 维护最近k个比本身大的数

ThreeWater-

于 2017-08-01 21:08:57 发布

阅读量877

点赞数

分类专栏：－－－Tip－－－

本文链接：https://blog.csdn.net/tree__water/article/details/76559497

版权

－－－Tip－－－专栏收录该内容

15 篇文章

订阅专栏

本文提供了一个使用C++编写的程序竞赛模板，通过具体的代码实现了读取整数、数组操作等功能，并通过预处理指令引入了标准库。该模板适用于算法竞赛中常见的问题解决策略，如数组元素位置追踪及特定条件下的累加计算。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
int read()
{
    int ret=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    for(; ch>='0'&&ch<='9'; ch=getchar()) ret=ret*10+ch-'0';
    return ret;
}
int pos[N],nxt[N],pre[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n=read(),m=read();
        for(int i=1; i<=n; i++)
        {
            int x=read();
            pos[x]=i,pre[i]=i-1,nxt[i]=i+1;
        }
        pre[0]=0;
        nxt[n+1]=n+1;
        ll sum=0;
        for(int j=1; j<=n; j++)
        {
            int x=pos[j];
            int rq[105];
            int lc,rc;
            lc=rc=0;
            for(int i=x;i<=n&&rc<m;i=nxt[i])
                rq[++rc]=nxt[i]-i;
            ll ans=0;
            for(int i=x; i>0&&lc<m; i=pre[i])
            {
                lc++;
                if(m-lc+1>rc) continue;
                else ans+=(i-pre[i])*rq[m-lc+1];
            }
            sum+=ans*j;
            pre[nxt[x]]=pre[x];
            nxt[pre[x]]=nxt[x];
        }
        printf("%I64d\n",sum);
    }
}