BZOJ2138 stone [Hall定理/线段树]

ajcxsu
ajcxsu 2018年09月20日
  • 49 次阅读

好难...

Problem

话说Nan在海边等人,预计还要等上M分钟。为了打发时间,他玩起了石子。Nan搬来了N堆石子,编号为1到N,每堆

包含Ai颗石子。每1分钟,Nan会在编号在[Li,Ri]之间的石堆中挑出任意Ki颗扔向大海(好疼的玩法),如果[Li,R

i]剩下石子不够Ki颗,则取尽量地多。为了保留扔石子的新鲜感,Nan保证任意两个区间[Li,Ri]和[Lj,Rj],不会

存在Li<=Lj&Rj<=Ri的情况,即任意两段区间不存在包含关系。可是,如果选择不当,可能无法扔出最多的石子,

这时NN就会不高兴了。所以他希望制定一个计划,他告诉你他m分钟打算扔的区间[Li,Ri]以及Ki。现在他想你告诉

他,在满足前i-1分钟都取到你回答的颗数的情况下,第i分钟最多能取多少个石子。

Solution

什么鬼输入...

考虑一个询问向一个区间连边,要求一个询问每次都得到一个能得到完备匹配的最大值。

显然这个最大值也许可以考虑二分或计算得到,现在问题在于如何验证是否存在完备匹配。

我们考虑霍尔定理。霍尔定理是原询问的一个子集,但此处不用。

我们假设将原询问右端点从小到大排序,对于询问的任意一个区间查看是否满足霍尔定理即可。
因为假设我们对于任意两个不相交区间询问,显然我们只需分别查看两个不相交区间是否符合条件即可。

那么问题在于我们怎么快速得知任意区间是否满足霍尔定理。

考虑维护石子个数前缀和$A_i$,令排序后询问选择的个数前缀和为$B_i$。令询问$i$询问石子的区间为$[L_i,R_i]$。

则对于任意$i\leq j$,存在: $$ B_j-B_{i-1} \le A_{R_j} - A_{L_i-1}$$ 整理得: $$ B_j-A_{R_j}\leq B_{i-1}-A_{L_i-1}$$

我们令$C_i=B_i-A_{R_i},D_i=B_{i-1}-A_{L_i-1}$,则化为对于任意$i\leq j$,存在: $$C_j \leq D_i$$

考虑这次选择的石子数$b_x=y$。那么对于$C_x$到$C_m$和$D_{x+1}$到$D_m$会整体加$y$。

则由于$j\geq i$,所以存在有$j \in [x,m], i \in [1, x], C_j+y\leq D_i$。

所以有$y\leq min(D_i-C_j)$。因此查询$[x,m]$中$C_j$的最大值和$[1,x]$中$D_i$的最小值即可。

感谢我一上午总算看懂了题解(里面虽然写错了一点)


PS:无需去除没被覆盖过的石子。
由于这只会让前缀和变得更大,因此会影响到两个不相交区间的询问判断(更可能符合霍尔定理),但事实上我们也会分解成两个相交区间的询问,所以我们可以直接(也确实会)忽略掉这类被影响的询问。

Code

// Code by ajcxsu
// Problem: stone

#include<bits/stdc++.h>
using namespace std;

const int N=4e5+10;
int a[N], S[N];

struct Query { int l, r, k, t; } q[N];
bool cmp(const Query &a, const Query &b) { return a.r<b.r; }
int idx[N];
bool cmp2(const int &a, const int &b) { return q[a].t<q[b].t; }

#define ls x<<1
#define rs x<<1|1
int C[N<<3], D[N<<3], lazyc[N<<3], lazyd[N<<3];
void pud(int x) {
    if(lazyc[x])
        C[ls]+=lazyc[x], C[rs]+=lazyc[x], lazyc[ls]+=lazyc[x], lazyc[rs]+=lazyc[x];
    if(lazyd[x])
        D[ls]+=lazyd[x], D[rs]+=lazyd[x], lazyd[ls]+=lazyd[x], lazyd[rs]+=lazyd[x];
    lazyc[x]=lazyd[x]=0;
}
void build(int x, int l, int r) {
    if(l==r) {  C[x]=-S[q[l].r], D[x]=-S[q[l].l-1]; return; }
    int mid=(l+r)>>1;
    build(ls, l, mid), build(rs, mid+1, r);
    C[x]=max(C[ls], C[rs]), D[x]=min(D[ls], D[rs]);
}
void updata(int x, int l, int r, int xl, int xr, int w, int t) {
    pud(x);
    if(xl<=l && r<=xr) { C[x]+=t?w:0, D[x]+=!t?w:0, lazyc[x]+=t?w:0, lazyd[x]+=!t?w:0; return; }
    int mid=(l+r)>>1;
    if(xl<=mid) updata(ls, l, mid, xl, xr, w, t);
    if(xr>mid) updata(rs, mid+1, r, xl, xr, w, t);
    C[x]=max(C[ls], C[rs]), D[x]=min(D[ls], D[rs]);
}
int queryc(int x, int l, int r, int xl, int xr) {
    pud(x);
    if(xl<=l && r<=xr) return C[x];
    int mid=(l+r)>>1;
    if(xr<=mid) return queryc(ls, l, mid, xl, xr);
    else if(xl>mid) return queryc(rs, mid+1, r, xl, xr);
    else return max(queryc(ls, l, mid, xl, mid), queryc(rs, mid+1, r, mid+1, xr));
}
int queryd(int x, int l, int r, int xl, int xr) {
    pud(x);
    if(xl<=l && r<=xr) return D[x];
    int mid=(l+r)>>1;
    if(xr<=mid) return queryd(ls, l, mid, xl, xr);
    else if(xl>mid) return queryd(rs, mid+1, r, xl, xr);
    else return min(queryd(ls, l, mid, xl, mid), queryd(rs, mid+1, r, mid+1, xr));
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, x, y, z, p;
    cin>>n>>x>>y>>z>>p;
    for(int i=1;i<=n;i++) a[i]=((i-x)*(i-x)+(i-y)*(i-y)+(i-z)*(i-z))%p, S[i]=a[i]+S[i-1];
    int m;
    cin>>m>>q[1].k>>q[2].k>>x>>y>>z>>p;
    if(!m) exit(0);
    for(int i=3;i<=m;i++) q[i].k=(x*q[i-1].k+y*q[i-2].k+z)%p;
    for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r, q[i].t=i, idx[i]=i;
    sort(q+1, q+1+m, cmp), sort(idx+1, idx+1+m, cmp2), build(1, 1, m);
    int b;
    for(int i=1;i<=m;i++) {
        b=min(queryd(1, 1, m, 1, idx[i])-queryc(1, 1, m, idx[i], m), q[idx[i]].k);
        updata(1, 1, m, idx[i], m, b, 1);
        if(idx[i]+1<=m) updata(1, 1, m, idx[i]+1, m, b, 0); // 注意...
        cout<<b<<endl;
    }
    return 0;
}

本文链接:https://acxblog.site/archives/sol-bzoj-2138.html
本文采用 CC BY-NC-SA 3.0 协议进行许可