牛客多校第九场D（二维差分，树状数组）

清初 / 2023-08-16 / 原文

1：题意：

找出所有的区间x，x里面的数的位置k不能是第k小

2：思路
对于一个确定的数字，考虑对于区间，如果这个导致了区间不合法，那一定是它是这个区间的第小。考虑左侧比大的个数，和右侧比小的数字个数，显然这两个要相等，及找出左大等于右小的个数，找出所有不合法的区间合并剩下的就是答案

3：二维差分

点击查看代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3+10;
int a[N];
vector<int>x[N],y[N];
int f[N][N];
void solve()
{
    int n;
    std::cin >> n;
    
    for(int i = 1;i <= n;i ++)
        std::cin >> a[i];
    
    for(int i = 1;i <= n;i ++)
    {
        int big = 0,small = 0;
        
        for(int j = i;j <= n;j ++)//右小
        {
            if(a[j]<a[i])
                small++;
            y[small].push_back(j);
        }
        
        for(int j = i;j>=1 ;j --)//左大
        {
            if(a[j] > a[i])
                big++;
            x[big].push_back(j);
        }
        
        for(int j = 0;j <= n;j ++)
        {
            if(x[j].size()!=0&&y[j].size()!=0)
            {
                f[x[j].back()][y[j].front()]++;//左下角
                f[x[j].back()][y[j].back()+1]--;
                f[x[j].front()+1][y[j].front()]--;
                f[x[j].front()+1][y[j].back()+1]++;//右上角
            }
            x[j].clear(),y[j].clear();
        }
    }

    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= n;j ++)
        {
            f[i][j] = f[i][j] + f[i-1][j] + f[i][j-1] - f[i-1][j-1];
        }
    }
    
    int ans = 0;
    for(int i = 1;i <= n;i ++)
        for(int j = i;j <= n;j ++)
            if(f[i][j] == 0)
                ans++;
    for(int i = 0;i <= n+1;i ++)
        for(int j = 0;j <= n+1;j ++)
            f[i][j] = 0;
    std::cout << ans << '\n';
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int t;
    std::cin >> t;
    while(t--)
        solve();
}

4：树状数组

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int T;
int n,a[N],pos[N][N],res,v[N],dp[N];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i))
        dp[i]+=v;
}
int ask(int x){
    int tot=0;
    for(int i=x;i;i-=lowbit(i))
        tot+=dp[i];
    return tot;
}
void solve(){
    res=0;
    cin>>n;
    for(int i=1;i<=n;i++)    v[i]=0;
    for(int i=1;i<=n;i++)    cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=n;j++)
            pos[i][j]=0;
    for(int i=1;i<=n;i++){
        int cnt=0;
        pos[i][cnt]=i;
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[i]){
                cnt++;
                pos[i][cnt]=j;
 //               cout<<i<<" "<<cnt<<" "<<j<<endl;
            }
        }
        pos[i][cnt+1]=n+1;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)    dp[j]=v[j]=0;
        for(int j=i;j<=n;j++){
            add(a[j],1);
            int num=ask(a[j]-1);
            int rank=j-i+1;
            int l=pos[j][rank-num-1];
            int r=pos[j][rank-num]-1;
            v[l]++;
            v[r+1]--;
        }
        int sum=0;
        for(int j=i;j<=n;j++){
            sum+=v[j];
            if(!sum)    res++;//,cout<<i<<" "<<j<<endl;;
        }
    }
    cout<<res<<endl;
}
int main(){
    cin>>T;
    while(T--)    solve();
    return 0;
}