「EZEC-2」数轴

君のNOIP。 · 2020-04-22 13:00:10 · 题解

先讲一下这题各种部分分的复杂度。

花式暴力：

• 8分，O(nm^3)

• 16分，O(nm^2)

• 24分，O(n^4)

• 32分，O(n^3)

• 40分，O(n^2logn)

• 48分，O(n^2)

送分结束。

认真骗分：

• 64分，在 O(n^2) 做法上加个小优化。

• 84分，数据结构：O(nklog^2 n) 或 O(nk^2logn)

简单正解：

• 100分，O(n(k+logn))

48分： O(n^2) 的暴力。

很显然，最优解一定是某两个有标记的点（包括 -1 和 m+1）之间的距离 -1 ，这两个点只需要满足他们之间（不包括这两个点）的标记数 \le k 即可。

所以我们只需枚举有标记的点作为左端点和右端点即可。

按照这个思路，我们可以直接用 set 和 map ，但是我不太会用。

如果用数组存，只需先离线记录各个输入，然后开个结构体排个序再 map 瞎搞搞就好了。

每次操作的时候，枚举左端点，将右端点不断向右挪就好了。

Code:

#include<bits/stdc++.h>
using namespace std;
int n, m, k;
int ans;
int num[10005], pos[10005], cnt;
struct node{
    int x, a;
} e[10005];
int x[10005], a[10005];
map<int,int>mp;

bool comp(node x,node y){
    return x.x < y.x;
}

int main(){
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++){
        cin>>e[i].x>>e[i].a;
        x[i] = e[i].x, a[i] = e[i].a;
    }
    e[n+1].x = -1;
    sort(e+1,e+2+n,comp);
    for(int i = 1; i <= n + 1; i++){
        if(e[i].x != pos[cnt]) pos[++cnt] = e[i].x;
        mp[e[i].x] = cnt;
    }
    pos[cnt+1] = m + 1;
    for(int i = 1; i <= n; i++){
        num[mp[x[i]]] += a[i];
        int t = 1, s = 0;
        ans = -1;
        for(int j = 1; j <= cnt; j++){
            s -= num[j];
            while(s + num[t+1] <= k && t < cnt) t++, s += num[t];
            ans = max(ans,pos[t+1] - pos[j] - 2);
        }
        cout<<ans<<endl;
    }
}

64分： O(n^2) 的暴力 + 优化。

• 保证测试点 13\sim 16 的 x_i 为随机构造。

很显然，每次操作的答案小于等于上次的答案。

其实在随机数据下，是会有很多相同的答案的。

因为随着操作的增多，答案区间也越来越小，需要更新答案的概率也就越低。

所以如果某次操作的答案与上次的相同，那么就不用再更新答案。

怎么判断某次的答案是不是与上次的相同呢？

我们每次操作后记录下当前答案区间的左右端点，很显然如果某次操作的 x_i 不在上次的答案区间内，就不用更新答案。

Code：

#include<bits/stdc++.h>
using namespace std;
#define MAX_N 1000005
int n, m, k;
int ll, rr;
int ans;
int num[MAX_N], pos[MAX_N], cnt;
struct node{
    int x, a;
}e[MAX_N];
int x[MAX_N], a[MAX_N];
map<int,int>mp;

bool comp(node x,node y){
    return x.x < y.x;
}

int main(){
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++){
        cin>>e[i].x>>e[i].a;
        x[i] = e[i].x, a[i] = e[i].a;
    }
    e[n+1].x = -1;
    sort(e+1,e+2+n,comp);
    for(int i = 1;i <= n + 1; i++){
        if(e[i].x != pos[cnt]) pos[++cnt] = e[i].x;
        mp[e[i].x]= c nt;
    }
    pos[cnt+1] = m+1;
    rr = m;
    for(int i = 1; i <= n; i++){
        num[mp[x[i]]] += a[i];
        if(x[i] >= ll && x[i] <= rr){
            int t = 1, s = 0;
            ans = -1;
            for(int j = 1; j <= cnt; j++){
                s -= num[j];
                while(s + num[t+1] <= k && t < cnt) t++, s += num[t];
                if(pos[t+1] - pos[j] - 2 > ans) ans = pos[t+1] - pos[j] - 2, ll = pos[j] + 1, rr = pos[t+1] - 1;
            }
        }
        cout<<ans<<endl;
    }
}

84分：数据结构。

• 方法一：万能的线段树 O(nk^2logn)

注意到 m\le 10^6 ，那么我们可以直接开线段树维护。

只需维护符合要求的最大区间，从左端点开始的最大区间，从右端点开始的最大区间。

考虑到 k\le 3 ，我们只需开二维，每个节点 k^2 暴力更新。

由于是单点修改，不需要下传标记。

询问也很简单，直接输出节点 1 的最大区间即可。

每次上传信息的时候，就维护下该区间内有 j 个标记时的最大区间，从左端点开始的最大区间，从右端点开始的最大区间即可。

所以这个连懒惰标记都不用的线段树就很好打了。

Code：

#include<map>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define G() Cr=getchar()
#define sum(i,j) tr[i].sum[j]
#define lst(i,j) tr[i].lst[j]
#define rst(i,j) tr[i].rst[j]
int Xr;char Cr;
inline int rd(){
    Xr=0, G();
    while(Cr<'0' || Cr>'9') G();
    while(Cr>='0' && Cr<='9') Xr=(Xr<<3) + (Xr<<1) + (Cr & 15), G();
    return Xr;
}
#define MAX_N 1000005
int n, m, k;
int ans;
int num[MAX_N];
int pos, a;

struct Node {
    int sum[5], lst[5], rst[5];
} tr[MAX_N<<2];

void Push_up(int i,int l,int r) {
    int mid = l + r >> 1;
    for(int j = 0; j <= k; j++)
        sum(i,j) = max(sum(i<<1,j),sum(i<<1|1,j)),
        lst(i,j) = lst(i<<1,j),
        rst(i,j) = rst(i<<1|1,j);
    for(int j = 0; j <= k; j++)
        for(int p = 0; p <= j; p++) {
            if(rst(i<<1,p) && lst(i<<1|1,j-p))sum(i,j) = max(sum(i,j), rst(i<<1,p) + lst(i<<1|1,j-p));
            if(lst(i<<1,p) == mid-l+1 && lst(i<<1|1,j-p)) lst(i,j) = max(lst(i,j), lst(i<<1,p) + lst(i<<1|1,j-p));
            if(rst(i<<1|1,p) == r-mid && rst(i<<1,j-p)) rst(i,j) = max(rst(i,j), rst(i<<1|1,p) + rst(i<<1,j-p));
        }
}

void Build(int i,int l,int r) {
    if(l == r) {
        sum(i,0) = lst(i,0) = rst(i,0) = 1;
        return;
    }
    int mid = l + r >> 1;
    Build(i<<1,l,mid);
    Build(i<<1|1,mid+1,r);
    Push_up(i,l,r);
}

void Change(int i,int l,int r,int P) {
    if(l>=P && r<=P) {
        for(int j=0;j<=k;j++) sum(i,j) = lst(i,j) = rst(i,j) = 0;
        if(num[l] <= k) sum(i,num[l]) = lst(i,num[l]) = rst(i,num[l]) = 1;
        return;
    }
    int mid = l + r >> 1;
    if(mid >= P) Change(i<<1,l,mid,P);
    else Change(i<<1|1,mid+1,r,P);
    Push_up(i,l,r);
}

int main() {
    n=rd(), m=rd(), k=rd();
    Build(1,0,m);
    for(int i = 1;i <= n;i++) {
        pos=rd(), a=rd();
        num[pos] += a;
        Change(1,0,m,pos);
        ans = -1;
        for(int j = 0;j <= k; j++) ans = max(ans,sum(1,j) - 1);
        printf("%d\n",ans);
    }
}

• 方法二：树状数组 + 二分 O(nklog^2n)

首先我们发现由于每次的答案小于等于上一次的答案，我们不能直接维护最大区间。

但如果将询问倒序处理呢？

我们发现答案变为大于等于上一次的答案。

这样问题就转化为每次删除若干标记。

这样还不够，我们发现每次如果更新答案，那么新的答案区间一定包含此处操作删除标记的那个点。

所以我们只需枚举最多 k 个左端点，我们可以用树状数组维护在某个最终有标记的点的标记数前缀和，然后利用二分查找枚举左右端点即可。

Code：

#include<map>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define G() Cr=getchar()
int Xr;char Cr;
inline int rd(){
    Xr = 0, G();
    while(Cr < '0' || Cr > '9') G();
    while(Cr >= '0' && Cr <= '9')Xr = (Xr<<3) + (Xr<<1) + (Cr & 15), G();
    return Xr;
}
#define LL long long
#define MAX_N 1000005
int n, m, k;
int ans[MAX_N];
int num[MAX_N], pos[MAX_N], cnt;
int ma = -1, s, t;
int sum[MAX_N];
struct node{
    int x, a;
} e[MAX_N];
int x[MAX_N], a[MAX_N];
map<int,int>mp;

bool comp(node x,node y){
    return x.x < y.x;
}

void add(int p,int x){
    while(p <= cnt) sum[p] += x, p += p & -p;
}

int gsum(int p){
    int ss=0;
    while(p) ss += sum[p], p -= p & -p;
    return ss;
}

int find_l(int p){
    int ss = gsum(p);
    int l=1, r=p, sss=p;
    while(l <= r){
        int mid = (l + r)>>1;
        if(ss - gsum(mid) <= k) sss = mid, r = mid - 1;
        else l = mid + 1;
    }
    return sss;
}

int find_r_j(int p){
    int ss = gsum(p);
    int l = p + 1, r = cnt, sss = p + 1;
    while(l <= r){
        int mid = (l + r)>>1;
        if(ss < gsum(mid)) sss = mid, r = mid - 1;
        else l = mid + 1;
    }
    return sss;
}

int find_r_t(int p){
    int ss = gsum(p);
    int l = p, r = cnt, sss = p;
    while(l <= r){
        int mid = (l + r)>>1;
        if(gsum(mid) - ss <= k) sss = mid, l = mid + 1;
        else r = mid - 1;
    }
    return sss;
}

int main(){
    n = rd(), m = rd(), k = rd();
    for(int i = 1; i <= n; i++) {
        e[i].x = rd(), e[i].a = rd();
        x[i] = e[i].x, a[i] = e[i].a;
    }
    e[n+1].x = -1;
    sort(e+1,e+2+n,comp);
    for(int i = 1; i <= n + 1; i++) {
        if(e[i].x != pos[cnt]) pos[++cnt] = e[i].x;
        mp[e[i].x] = cnt;
    }
    pos[cnt+1] = m + 1;
    for(int i = 1; i <= n; i++) num[mp[x[i]]] += a[i], add(mp[x[i]],a[i]);
    for(int i = 1; i <= cnt; i++) {
        s -= num[i];
        while(s + num[t+1] <= k && t < cnt) t++, s += num[t];
        ma=max(ma,pos[t+1] - pos[i] - 2);
    }
    ans[n] = ma;
    for(int i = n; i >= 2; i--) {
        int p = mp[x[i]];
        add(p,-a[i]);
        int j = find_l(p), t;
        while(j < p){
            t = find_r_t(j);
            ma = max(ma,pos[t+1] - pos[j] - 2);
            j = find_r_j(j);
        }
        ans[i-1] = ma;
    }
    for(int i = 1; i <= n; i++) printf("%d\n",ans[i]);
}

100分：O(n(k+logn)) 只需开几个数组直接维护即可 。

考虑反正每次也是最多枚举 k 次左端点，我们可以定两个数组 l_i,r_i，表示第 i 个最终有标记点的左边和右边的第一个有标记的点的下标。

初始化：

l[i] = i - 1, r[i] = i + 1;

然后每次倒序操作时，若此点的标记减为 0， 更新 ：

if(!num[p]) r[l[p]] = r[p], l[r[p]] = l[p];

其中 p 为此次操作删去标记的点。

然后查询也就只需每次移动到 l_j,r_j 即可，很显然每次操作移动复杂度为 O(k)

Code:

#include<map>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define G() Cr=getchar()
int Xr;char Cr;
inline int rd(){
    Xr = 0, G();
    while(Cr < '0' || Cr > '9') G();
    while(Cr >= '0' && Cr <= '9') Xr = (Xr<<3) + (Xr<<1) + (Cr & 15), G();
    return Xr;
}
#define MAX_N 1000005
int n, m, k;
int ans[MAX_N];
int num[MAX_N], pos[MAX_N], cnt;
int l[MAX_N], r[MAX_N];
int ma = -1, s, t;
struct node{
    int x, a;
} e[MAX_N];
int x[MAX_N], a[MAX_N];
map<int,int>mp;

bool comp(node x,node y){
    return x.x < y.x;
}

int main(){
    n = rd(), m = rd(), k = rd();
    for(int i = 1; i <= n; i++) {
        e[i].x = rd(), e[i].a = rd();
        x[i] = e[i].x, a[i] = e[i].a;
    }
    e[n+1].x = -1;
    sort(e+1,e+2+n,comp);
    for(int i = 1; i <= n + 1; i++) {
        if(e[i].x != pos[cnt]) pos[++cnt] = e[i].x;
        mp[e[i].x] = cnt;
    }
    pos[cnt+1] = m + 1;
    for(int i = 1; i <= n; i++) num[mp[x[i]]] += a[i];
    for(int i = 1; i <= cnt; i++) {
        s -= num[i];
        while(s + num[t+1] <= k && t < cnt) t++, s += num[t];
        ma = max(ma, pos[t+1] - pos[i] - 2);
        l[i] = i - 1, r[i] = i + 1;
    }
    ans[n] = ma;
    for(int i = n; i >= 2; i--) {
        int p = mp[x[i]];
        num[p] -= a[i];
        if(!num[p]) r[l[p]] = r[p], l[r[p]] = l[p];
        t = p;
        int j = p;
        s = num[t];
        while(j > 1 && s <= k) j = l[j], s += num[j];
        for(j; j < p; j = r[j]) {
            s -= num[j];        
            while(s + num[r[t]] <= k && r[t] <= cnt) t = r[t], s += num[t];
            ma = max(ma, pos[r[t]] - pos[j] - 2);
        }
        ans[i-1] = ma;
    }
    for(int i = 1; i <= n; i++) printf("%d\n",ans[i]);
}

总结：这是一道思维题，细节也不少，不过部分分非常足。

另：我是用 map 的，所以会比较慢， std 被吊打很正常/kk