Codeforces Round #136 (Div. 1)E(尺取法+树状数组)

83 阅读 0 评论 55 点赞

我是靠谱客的博主粗暴水杯，这篇文章主要介绍Codeforces Round #136 (Div. 1)E(尺取法+树状数组)，现在分享给大家，希望可以做个参考。

题目链接：https://codeforces.com/contest/220/problem/E

题意：只保留a数列中1..l和r..n的数构成b数列，然后b数列的逆序对数小于等于k.问这样的l,r的对数。

分析：树状数组+尺取

枚举l,每次找到最小的满足题意的r，对答案的贡献是n-r+1,然后用两个树状数组，分别维护增加或者减少一个数的时候，前半段和后半段对逆序数的影响。

Ac code:

复制代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
ll c[2][maxn];
int a[maxn],n;
vector<int>p;
int lowbit(int x)
{
    return x&(-x);
}
void update(bool flag,int x,ll val)
{
    if(!flag) x=n-x+1;
    while(x<=n){
        c[flag][x]+=val;
        x+=lowbit(x);
    }
}
ll query(bool flag,int x)
{
    if(!flag) x=n-x+1;
    ll ans=0;
    while(x>0){
        ans+=c[flag][x];
        x-=lowbit(x);
    }
    return ans;
}
int Hash(int x)
{
    return lower_bound(p.begin(),p.end(),x)-p.begin()+1;
}
int main()
{
    ll k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i],p.push_back(a[i]);
    sort(p.begin(),p.end());
    p.erase(unique(p.begin(),p.end()),p.end());
    ll ans=0,cnt=0;
    for(int i=n;i>=1;--i)///起初l==r,b数组就是a数组,逆序对数就是a数组的逆序对数
    {
        a[i]=Hash(a[i]);
        cnt+=query(1,a[i]-1);///倒着求<a[i]的数那么刚好就是逆序对
        update(1,a[i],1);
    }
    int r=1;
    for(int l=1;l<=n;l++)
    {
        cnt+=query(0,a[l]+1)+query(1,a[l]-1);///query(0,x)表示查询大于>=x的数的个数,query(1,x)表示查询<=x的数的个数
        update(0,a[l],1);///左端点增加,插入a[l]
        while((r<=l||cnt>k)&&r<=n){
            cnt-=query(0,a[r]+1)+query(1,a[r]-1);///不满足条件时右端点右移,找到最小的满足条件的r
            update(1,a[r],-1);
            ++r;
        }
        ans+=n-r+1;///如果r继续右移逆序对数会减少,所以后面肯定满足条件,故答案可以直接加上n-r+1
    }
    cout<<ans<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
ll c[2][maxn];
int a[maxn],n;
vector<int>p;
int lowbit(int x)
{
    return x&(-x);
}
void update(bool flag,int x,ll val)
{
    if(!flag) x=n-x+1;
    while(x<=n){
        c[flag][x]+=val;
        x+=lowbit(x);
    }
}
ll query(bool flag,int x)
{
    if(!flag) x=n-x+1;
    ll ans=0;
    while(x>0){
        ans+=c[flag][x];
        x-=lowbit(x);
    }
    return ans;
}
int Hash(int x)
{
    return lower_bound(p.begin(),p.end(),x)-p.begin()+1;
}
int main()
{
    ll k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i],p.push_back(a[i]);
    sort(p.begin(),p.end());
    p.erase(unique(p.begin(),p.end()),p.end());
    ll ans=0,cnt=0;
    for(int i=n;i>=1;--i)///起初l==r,b数组就是a数组,逆序对数就是a数组的逆序对数
    {
        a[i]=Hash(a[i]);
        cnt+=query(1,a[i]-1);///倒着求<a[i]的数那么刚好就是逆序对
        update(1,a[i],1);
    }
    int r=1;
    for(int l=1;l<=n;l++)
    {
        cnt+=query(0,a[l]+1)+query(1,a[l]-1);///query(0,x)表示查询大于>=x的数的个数,query(1,x)表示查询<=x的数的个数
        update(0,a[l],1);///左端点增加,插入a[l]
        while((r<=l||cnt>k)&&r<=n){
            cnt-=query(0,a[r]+1)+query(1,a[r]-1);///不满足条件时右端点右移,找到最小的满足条件的r
            update(1,a[r],-1);
            ++r;
        }
        ans+=n-r+1;///如果r继续右移逆序对数会减少,所以后面肯定满足条件,故答案可以直接加上n-r+1
    }
    cout<<ans<<endl;
    return 0;
}