codeforces1870C

codeforces1870C

题意

给你两个整数 和 。同时给你一个大小为 的整数数组 。已知对于所有 ， .

定义大小为 的二维数组 如下：.将数组表示为一个正方形，其中左上角的单元格为，行的编号从上到下从到，列的编号从左到右从到。让一个单元格的颜色就是写在其中的数字(坐标为的单元格的颜色是) .

对于从 到 的每种颜色，找出数组 中包含该颜色所有单元格的最小矩形。输出该矩形的宽和高之和 .

方法 一

求最左边和最右边大于等于的数的下标, 即 。

#include<iostream>
#include<vector>
using namespace std;
const int N=100005;
int le[N],ri[N];
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        vector<int>a(n+1);
        vector<bool>st(k+1);
        for(int i=1;i<=n;i++) cin>>a[i],st[a[i]]=true;
        int now=0;
        for(int i=1;i<=n;i++){
            while(now<a[i]) le[++now]=i; //求最左边大于等于a[i]的数的下标
        }
        now=0;
        for(int i=n;i>=1;i--){
            while(now<a[i]) ri[++now]=i; //求最右边大于等于a[i]的数的下标
        }
        for(int i=1;i<=k;i++){
            cout<<(st[i]?(ri[i]-le[i]+1)*2:0)<<" ";
        }
        cout<<endl;
    }
    return 0;
}