2019牛客暑期多校训练营(第七场)E

作者: ffacs 分类: 题目 发布时间: 2019-12-31 03:42

Problem Description

对于一个初始为空的数组,有\(n\)次操作,每次给定区间\([L_i,R_i]\),将区间中的数插入数组中,并且输出中位数。

We define: $ Xi=(A1×X_{i−1}+B1×X_{i−2}+C1) module M1$ \(Yi=(A2×Y_{i−1}+B2×Y_{i−2}+C2) module M2\) We also define: \(Li=min(Xi,Yi)+1\), \(for \ i=1 \ to \ N.\) \(Ri=max(Xi,Yi)+1\), \(for \ i=1 \ to \ N.\)

Input

格式为:

\[n \\X1 \ X2 \ A1 \ B1 \ C1 \ M1 \\Y1 \ Y2 \ A2 \ B2\ C2 \ M2 \\Limits:1 \leq N \leq 400000 \\0 \leq A_1 < M_1 \\0 \leq A_2 < M_2\\0 \leq B_1 < M_1\\0 \leq B_2 < M_2\\0 \leq C_1 < M_1\\0 \leq C_2 < M_2\\0 \leq X_1 < M_1\\0 \leq X_2 < M_1\\0 \leq Y_1 < M_2\\0 \leq Y_2 < M_2\\1 \leq M_1 \leq 10^9\\1 \leq M_2 \leq 10^9\] ## Output

You should output \(N\) lines. Each line contains an integer means the median.

Solution

刚开始拿到题有几个思路,一个是差分前缀和+二分,一个是权值线段树,后来只写了权值线段树。

发现端点的值域是\([1,1e9+1]\),那么直接按值域建一颗权值线段树是不太可行的(也许动态开点可以水过去)。考虑离散化。我们可以用叶子上的点表示区间,因为每次的修改区间我们是可以预处理得到的,同时,我们只会去修改两个端点间的区间。端点又最多是\(2N\)。那么初步的想法有了:先把全部区间都算出来,再把端点排序离散化,再建线段树。接下来就是扣细节。

  • 每个叶子对应的区间应该如何分割
    • 对于排完序的端点,假设其为\(a,b,c,d,e...z\),线段树叶子的表示区间为\((a,b-1),(b,c-1),(c,d-1)\).....
    • 更新到叶子的时候肯定要是完整的区间被更新,所以对于每个修改,被涉及到的叶子都应该被包含在区间里面
    • 每个修改的右端点应该作为叶子表示区间的右端点。很容易理解,如果修改区间的右端点不是叶子表示区间的右端点,那么我们要修改包含这个右端点的区间的时候,对于叶子,就有一些要被修改,有一些不要被修改,这就出事了
    • 所以,我们想到一个解决方案,离散化的时候,不是离散化左右端点,而是离散化左端点和右端点+1,这样就能保证每个右端点都是叶子表示区间的右端点。
  • 如何修改与查询
    • 线段树记录的是所表示区间内数字出现次数的和
  • 用tag标签表示子树区间每个数字需要加上的次数
    • 对于叶子节点的tag标签,它能够表示所表示区间内每个数字所加上的次数,因为叶子表示区间内数字加的次数是相同的
    • 假设当前要查询第k个
      • 如果当前是叶子,返回表示区间左端点+\((k-1)/tag\)
      • 否则如果左子树数字出现次数的和小于k则到右子树找第\(k-sum\)[左子树]个数
      • 否则到左子树找第k个

分析得很清楚了,接下来就是具体实现的问题了

AC代码

#include <bits/stdc++.h>
#define rg register
#define MEM(NAME) memset(NAME,0,sizeof NAME)
using namespace std;
typedef long long ll;
template<typename T>
inline bool read(T &n) {
    T ans = 0, flag = 1;
    char ch;
    while ((ch = getchar()) < '0' || ch > '9') if (ch == '-') flag = -1; else if (ch == EOF) return false;
    ans = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9') ans = ans * 10 + ch - '0';
    n = ans * flag;
    return true;
}
inline ll read() {
    ll ans = 0, flag = 1;
    char ch;
    while ((ch = getchar()) < '0' || ch > '9') if (ch == '-') flag = -1;
    ans = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9') ans = ans * 10 + ch - '0';
    return ans * flag;
};
const int maxn=1000005;
ll y[maxn],x[maxn],a1,a2,b1,b2,c1,c2,m1,m2,n;
int vl[maxn],vr[maxn];
vector<int> v;
unordered_map<int,int> M;
void init(){//初始离散化
    cin>>n;
    cin>>x[1]>>x[2]>>a1>>b1>>c1>>m1;
    cin>>y[1]>>y[2]>>a2>>b2>>c2>>m2;
    for(rg int i=3;i<=n;i++){
        x[i]=(a1*x[i-1]+b1*x[i-2]+c1)%m1;
        y[i]=(a2*y[i-1]+b2*y[i-2]+c2)%m2;
    }
    for(rg int i=1;i<=n;i++){
        vl[i]=min(x[i],y[i])+1;
        vr[i]=max(x[i],y[i])+1;
        v.push_back(vl[i]),v.push_back(vr[i]+1);
    }
    sort(v.begin(),v.end());//左端点和(右端点+1)排序
    v.erase(unique(v.begin(),v.end()),v.end());//去重
    for(rg int i=0;i<v.size();i++){
        M[i+1]=v[i];//离散化,用map对应一下
    }
}
ll tree[maxn<<3];int tag[maxn<<3],lv[maxn<<3],rv[maxn<<3];
void build(int l,int r,int tl,int tr,int p){
    lv[p]=tl,rv[p]=tr;//记录当前结点对应的区间
    if(l==r) {
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,tl,M[mid+1]-1,p<<1);
    build(mid+1,r,M[mid+1],tr,p<<1|1);
}
inline void cg(ll k,int p) {//修改结点函数
    tag[p]+=k;
    tree[p]+=(rv[p]-lv[p]+1)*k;
}
inline void pushup(int p){//更新函数
    tree[p]=tree[p<<1]+tree[p<<1|1];
}
inline void pushdown(int p){//tag下传
    cg(tag[p],p<<1);
    cg(tag[p],p<<1|1);
    tag[p]=0;
}
void update(int k,int l,int r,int p){
    if(lv[p]>=l&&rv[p]<=r){
        cg(k,p);
        return;
    }
    if(tag[p]) pushdown(p);
    if(l<=rv[p<<1]) update(k,l,r,p<<1);
    if(r>=lv[p<<1|1]) update(k,l,r,p<<1|1);
    pushup(p);
}
int query(ll k,int nl,int nr,int p){
    if(nl==nr){
        return lv[p]+(k-1)/tag[p];
    }
    if(tag[p]) pushdown(p);
    int mid=(nl+nr)>>1;
    if(tree[p<<1]>=k) return query(k,nl,mid,p<<1);
    else return query(k-tree[p<<1],mid+1,nr,p<<1|1);
}
int main() {
//    freopen("/home/ffacs/Codes/Ccodes/testin.txt","r",stdin);
//    freopen("/home/ffacs/Codes/Ccodes/testout.txt","w",stdout);
    init();
    build(1,v.size(),M[1],M[v.size()],1);
    for(rg int i=1;i<=n;i++){
        update(1,vl[i],vr[i],1);
        printf("%d\n",query((tree[1]+1LL)/2,1,v.size(),1));
    }
    return 0;
}

顺便给出对拍用的造数据程序

#pragma GCC optimiz(O2)
#include <bits/stdc++.h>
#define rg register
#define MEM(NAME) memset(NAME,0,sizeof NAME)
using namespace std;
typedef long long ll;
template<typename T>
inline bool read(T &n) {
    T ans = 0, flag = 1;
    char ch;
    while ((ch = getchar()) < '0' || ch > '9') if (ch == '-') flag = -1; else if (ch == EOF) return false;
    ans = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9') ans = ans * 10 + ch - '0';
    n = ans * flag;
    return true;
}
inline ll read() {
    ll ans = 0, flag = 1;
    char ch;
    while ((ch = getchar()) < '0' || ch > '9') if (ch == '-') flag = -1;
    ans = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9') ans = ans * 10 + ch - '0';
    return ans * flag;
};
const int maxn=1e5+5;
int n;
int main(){
    freopen("/home/ffacs/Codes/Ccodes/testin.txt","w",stdout);
    srand(time(0));
    const int x=1e9;
    int n=rand()%400000+1;
    int m1=rand()%x+1,m2=rand()%x+1;
    int x1=rand()%m1+1,x2=rand()%m1+1,a1=rand()%m1,b1=rand()%m1,c1=rand()%m1;
    int y=rand()%m1+1,y2=rand()%m1+1,a2=rand()%m1,b2=rand()%m1,c2=rand()%m1;
    cout<<n<<endl;
    cout<<x1<<' '<<x2<<' '<<a1<<' '<<b1<<' '<<c1<<' '<<m1<<endl;
    cout<<y<<' '<<y2<<' '<<a2<<' '<<b2<<' '<<c2<<' '<<m2<<endl;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注