CF790 div4 F(双指针） H（逆序对）

- 日理万妓 2024-03-27 10:24 20阅读 0赞

**乐，被div4薄纱了**

**没想到把所有出现次数>=k的数放一个数组里然后双指针**

**还有H，连逆序对都没看出来，嘻**

**感觉以后还是写写div4算了，写什么div2啊，caibi**

[Problem - F - Codeforces][]

题意：

给定一个数列，长度为n，有一个数k，问使得值域在\[l,r\]的数中在数列中出现次数>=k的最大的r-l+1是多少

思路：

首先这个数列和顺序无关，所以可以把它看成集合，这道题多半要用到哈希，因此先用map统计出每个数的出现次数

因为要求在值域中的最大区间，所以考虑在哈希表里面做双指针

但是值域上限是1e9，无论是时间还是空间都不支持

但是我们注意到有一句话：

![b816949b852b5f97a0ba67f2fac11fe3.png][]

所以复杂度和n有关系

所以应该想到把所有出现次数>=k的数放在一个数组里，然后双指针去找最大连续区间长度就好了

感觉双指针有两种写法，一种是尺取法，另一种就是这道题的while(1)写法

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define low(x) (x&(-x))
    const int mxn=2e5+10,mxe=2e5+10;
    int n,k;
    void solve(){
        cin>>n>>k;
        map<int,int> mp;
        vector<int> v;
        vector<int> a(n+10);
        for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;
        for(auto it:mp){
            if(it.second>=k) v.push_back(it.first);
        }
        if(v.empty()){
            cout<<-1<<'\n';
            return;
        }
        sort(v.begin(),v.end());
        int l=0,r=0,sz=v.size(),ans=-1,ansl,ansr;
        while(1){
            if(l>sz-1||r>sz-1) break;
            while(r<=sz-1&&v[r]-v[l]==r-l) r++;
            if(ans<r-1-l+1){
                ans=r-1-l+1;
                ansl=v[l];
                ansr=v[r-1];
            }
            l=r;
            r++;
        }
        if(ans<v[r-1]-v[l]) ansl=v[l],ansr=v[r-1];
        cout<<ansl<<" "<<ansr<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

然后是H

[Problem - H2 - Codeforces][]

题意：感觉不如直接放出来，看图比较直观

![a70aff267c99da4492ac36d46fc10e11.png][]

一眼逆序对了，但是我没看出来，嘻

用树状数组维护就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define low(x) (x&(-x))
    const int mxn=2e5+10,mxe=2e5+10;
    int n;
    int a[mxn];
    struct BIT{
        int bitree[mxe];
        void init(){
            for(int i=0;i<=n;i++) bitree[i]=0;
        }
        int sum(int x){
            int res=0;
            for(int i=x;i;i-=low(i)) res+=bitree[i];
            return res;
        }
        void insert(int pos,int x){
            for(int i=pos;i<=n;i+=low(i)) bitree[i]+=x;
        }
    };
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        reverse(a+1,a+1+n);
        BIT tr;
        tr.init();
        int ans=0;
        for(int i=1;i<=n;i++){
            ans+=tr.sum(a[i]);
            tr.insert(a[i],1ll);
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - F - Codeforces]: https://codeforces.com/contest/1676/problem/F
[b816949b852b5f97a0ba67f2fac11fe3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/5e2cddd208374d079f811cf2c53b0e4f.png
[Problem - H2 - Codeforces]: https://codeforces.com/contest/1676/problem/H2
[a70aff267c99da4492ac36d46fc10e11.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/7786735c76e043be90efffae55dfadab.png