D - Online games【离散化差分】

题目链接：https://atcoder.jp/contests/abc221/tasks/abc221_d

题目大意：

给定 $nn$n 个区间 $A_i,B_{i}A\_i,B\_i$Ai​,Bi​ ，输出 $nn$n 个数，分别代表被 $1，2，...,n1，2，...,n$1，2，...,n 段区间覆盖的点有多少个。

$1\le n\le 2\times 10^5,1\le A_i,B_i\le 10^{9}1\; \backslash le\; n\; \backslash le\; 2\backslash times\; 10^5,1\; \backslash le\; A\_i,B\_i\; \backslash le\; 10^9$1≤n≤2×105,1≤Ai​,Bi​≤109

eg：共3个区间 $[1,2],[2,4],[3,3][1,2],[2,4],[3,3]$[1,2],[2,4],[3,3]

每个点被覆盖次数如下：

1	2	3	4
1	2	2	1

输出 ：2 2 0（被1段区间覆盖的点为1和4，2段覆盖的点为2和3，没有被三段区间覆盖的点）

思路：

$~~~~~~~~$        正常看就是差分板子题，但是由于 $A_i,B_{i}A\_i,B\_i$Ai​,Bi​ 最大到 $10^{9}10^9$109 ，直接差分数组开不下，所以加上离散化。离散化的主要操作在于把所有的数放进一个vector，然后进行去重操作。

vector<int>a;
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());

获得对应原数组第i个数的下标

int idx = lower_bound(v.begin(),v.end(),a[i])-v.begin();

$~~~~~~~~$        用离散化后的下标做差分，差分数组就只需要开到 4e5 就可以正常操作了，之后就用差分数组还原真实数组累加计算答案即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll ;
#define int ll
const int N=1e6+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f3f3f;
#define endl '\n'
#define cwkr     freopen("D:\\workplace\\CLion\\untitled\\in.in","r",stdin)
#define cwkw     freopen("D:\\workplace\\CLion\\untitled\\out.out","w",stdout)
using namespace std;
typedef pair<int, int> PII;
int n,m,k,a[N],b[N],c[N],num[N];
vector<int>v;
void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        b[i]+=a[i];
        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=0;i<n;i++){
        int idx=lower_bound(v.begin(),v.end(),a[i])-v.begin();
        c[idx]++;
        idx=lower_bound(v.begin(),v.end(),b[i])-v.begin();
        c[idx]--;
    }
    for(int i=1;i<v.size();i++) c[i]+=c[i-1];
    for(int i=0;i<v.size()-1;i++){
        int x=c[i];
        int y=v[i+1]-v[i];
        num[x]+=y;
    }
    for(int i=1;i<=n;i++) cout<<num[i]<<" ";
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    //cwkr;
    //cwkw;
    int _=1;
    //cin>>_;
    while(_--){
        solve();
    }
    return 0;
}

E - LEQ【树状数组】

题目链接：https://atcoder.jp/contests/abc221/tasks/abc221_e)

Tips：最好先掌握树状数组求逆序对

题目大意:

给定一个长度为 $nn$n 的序列 $AA$A ，找出一个长度为 $k(k\ge 2)k(k\backslash geq\; 2)$k(k≥2) 的序列 $A^{\prime }A\text{'}$A′ 使得$A_1^{\prime }\le A_k^{\prime }A\text{'}\_1\; \backslash le\; A\text{'}\_k$A1′​≤Ak′​ 。

$2\le n\le 3\times 10^{5}2\; \backslash le\; n\; \backslash le\; 3\backslash times\; 10^5$2≤n≤3×105 ， $1\le A_i\le 10^{9}1\; \backslash le\; A\_i\; \backslash le\; 10^9$1≤Ai​≤109

思路：

假设 Ax​≤Ay​(x<y) ，$A_{x}A\_x$Ax​ 为 $A_1^{\prime }A\text{'}\_1$A1′​ ， $A_{y}A\_y$Ay​ 为 $A_k^{\prime }A\text{'}\_k$Ak′​ 。那么 $xyxy$xy 中间的 $y-x-1y-x-1$y−x−1 个数可选可不选，即以 $A_{x}A\_x$Ax​ 开头 $A_{y}A\_y$Ay​ 结尾的序列有 $2^{y-x-1}2^\{y-x-1\}$2y−x−1 种。此时问题就变成了求 ${\sum }_{x=1}^n{\sum }_{y=x+1}^n[A_x\le A_y]2^{y-x+1}\backslash sum\backslash limits\_\{x=1\}^n\backslash sum\backslash limits\_\{y=x+1\}^n\; [A\_x\; \backslash le\; A\_y]\; 2^\{y-x+1\}$x=1∑n​y=x+1∑n​[Ax​≤Ay​]2y−x+1 的值。

最朴素的想法就是两层循环暴力计算，但是复杂度肯定过不去。已知树状数组求逆序对可以解决 ${\sum }_{x=1}^n{\sum }_{y=x+1}^n[A_x\ge A_y]\backslash sum\backslash limits\_\{x=1\}^n\backslash sum\backslash limits\_\{y=x+1\}^n\; [A\_x\; \backslash geq\; A\_y]$x=1∑n​y=x+1∑n​[Ax​≥Ay​] 的问题，那么就只需要在此基础上维护 $A_x\le A_{y}A\_x\; \backslash le\; A\_y$Ax​≤Ay​ 的情况和次方信息即可。

更改时：对于 $A_{x}A\_x$Ax​ ，在树状数组的对应位置上加上 $2^{n-x-1}2^\{n-x-1\}$2n−x−1 次方。

计算时：枚举 $xx$x ，用树状数组求 ${\sum }_{y=x+1}^n[A_x\le A_y]2^y\backslash sum\backslash limits\_\{y=x+1\}^n[A\_x\backslash le\; A\_y]\; 2^y$y=x+1∑n​[Ax​≤Ay​]2y 的值再乘 $2^{-x+1}2^\{-x+1\}$2−x+1 。

AC代码：

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int MAX=3e5+10;
const int mod = 998244353;
int n,tree[MAX],a[MAX],c[MAX],di[MAX];
int sum(int x){
    int ans=0;
    while(x){
        ans+=tree[x];
        ans%=mod;
        x-= lowbit(x);
    }
    return ans;
}
void add(int x,int d){
    while(x<=n){
        tree[x]+=d;
        tree[x]%=mod;
        x+= lowbit(x);
    }
}
int inv(int a){
    if(a == 1)return 1;
    return inv(mod%a)*(mod - mod/a)%mod;
}
vector<int> v;
void solve(){
    cin>>n;
    c[0]=1;
    for(int i=1;i<=n;i++){
        c[i]=(c[i-1]*2)%mod;
    }
    for(int i=0;i<n;i++){
        cin>>a[i];
        v.push_back(a[i]);
    }
    //离散化
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int shu=0;
    for(int i=0;i<n;i++){
        int idx=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
        int ans=sum(idx);
        ans=(ans*inv(c[n-i]))%mod;
        shu+=ans;
        shu%=mod;
        add(idx,c[n-i-1]);
    }
    cout<<shu;
}

signed main() {
    int _=1;
    //cin>>_;
    while(_--){
        solve();
    }
    return 0;
}