Codeforces-961E

发表于 | 分类于 | 浏览 次

题解

一般自己能独立做出的题目是不写题解的，但是这是我第一道独立做出的自己总结的 树状数组解决两个不等式限制问题 ，因此写篇题解纪念一下
设输入数据为$a_1····a_n$,若一个$(i,j)$对(设$i<j$)满足题目条件，则需满足三个条件
$$
\begin{cases}
i<j\\a[j]\ge i\\a[i]\ge j
\end{cases}
\implies
\begin{cases}
j\le min(a[i],i-1) \\ a[j]\ge i
\end{cases}
$$
化简后变为两个条件
从1到n循环
每轮循环更新update(i,1)，这样树状数组中每个为1的点都代表一个$j$
同时de[a[i]].push_back(i)，这样当$i$递增到$a[i]$时，下轮循环$i$递增不再满足$a[j]\ge i$，此时de[i]中有应该删除的$j$点，对这些点update(j,-1)即可保证树状数组中的点都满足第二个条件。
再通过sum(min(a[i],i-1))完成对第一个条件的限制，可求得同时满足两个条件的$j$点的个数,问题得解。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=2e5+100;

ll BIT[MAXN];
ll Lowbit(ll x)  // 2^k
{
    return x&(-x);
}
void update(ll i, ll x)//i点增量为x
{
    while(i <MAXN)
    {
        BIT[i] += x;
        i += Lowbit(i);
    }
}
ll sum(ll x)//区间求和 [1,x]
{
    ll sum=0;
    while(x>0)
    {
        sum+=BIT[x];
        x-=Lowbit(x);
    }
    return sum;
}
std::vector<int> de[MAXN];
ll a[MAXN],show[MAXN];
int main(int argc, char const *argv[]) {
    // freopen("input.txt","r",stdin);
    ll n;
    ll ans=0;
    ll up=2e5;
    std::cin >> n;
    memset(BIT,0,sizeof BIT);
    memset(show,0,sizeof show);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        if(a[i]>i)update(i,1);
        show[i]++;
        if(i>1)
            ans+=sum(min(i-1LL,a[i]));
        if(a[i]>i && a[i]<MAXN)de[a[i]].push_back(i);
        for(ll v:de[i])
            update(v,-1),show[v]--;
    }
    cout<<ans<<endl;
    return 0;
}

其他总结的“树状数组满足两个不等式限制问题”的题解

ZOJ 4008 Yet Another Tree Query Problem
HDU-6230 HDU-5542 利用树状数组解决两个不等式限制的问题