洛谷P4065 [JXOI2017]颜色(线段树)

作者: 编程技术  发布:2019-09-20

题意

题目链接

题意:给一个$ntimes m$的网格,初始时有些地方不能选,给$k$个询问$(x,y)$,每次令$(x,y)$不能选,然后询问最大子正方形的边长

Sol

线段树板子题都做不出来,真是越来越菜了。。

根据题目描述,一个合法区间等价于在区间内的颜色没有在区间外出现过。

所以我们可以对于每个右端点,统计最长的左端点在哪里,刚开始以为这个东西有单调性,但事实并不是这样。。

我们统计出对于每个颜色最优的位置和最左的位置

那么对于某个左端点,如果(r_j > i),那么以及它左侧的点都是不能选的,这里可以用堆+multiset维护。

若(r_j leqslant i),那么((l_j, r_j])都是不能选的。

然后直接线段树区间赋值就好了

// luogu-judger-enable-o2#include<bits/stdc++.h>#define Fin freopen(#x".in", "r", stdin);#define Pair pair<int, int>#define fi first#define se second template<typename A, typename B> inline bool chmax(A &x, B y) {return x < y ? x = y, 1 : 0;}template<typename A, typename B> inline bool chmin(A &x, B y) {return x > y ? x = y, 1 : 0;}#define LL long long using namespace std;const int MAXN = 2e6 + 10, INF = 1e9 + 10;inline int read() {    char c = getchar(); int x = 0, f = 1;    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int N, a[MAXN], r[MAXN], l[MAXN], tag[MAXN];multiset<int> s;priority_queue<Pair, vector<Pair>, greater<Pair> > q;void Erase {    auto it = s.find;    s.erase;}#define ls k << 1#define rs k << 1 | 1int f[MAXN], sum[MAXN];void update {    sum[k] = sum[ls] + sum[rs];}void ps {    sum[k] = 0; f[k] = 1;}void pushdown {    if return ;    ps; ps;    f[k] = 0;}void Build(int k, int l, int r) {    f[k] = 0;     if {sum[k] = 1; return ;}    int mid = l + r >> 1;    Build(ls, l, mid); Build(rs, mid + 1, r);    update;}int Query(int k, int l, int r, int ql, int qr) {    if(ql <= l && r <= qr) return sum[k];    pushdown;    int mid = l + r >> 1;    if(ql > mid) return Query(rs, mid + 1, r, ql, qr);    else if(qr <= mid) return Query(ls, l, mid, ql, qr);    else return Query(ls, l, mid, ql, qr) + Query(rs, mid + 1, r, ql, qr);}void Mem(int k, int l, int r, int ql, int qr) {    if(ql <= l && r <= qr) {ps; return ;}    pushdown;    int mid = l + r >> 1;    if(ql <= mid) Mem(ls, l, mid, ql, qr);    if(qr  > mid) Mem(rs, mid + 1, r, ql, qr);    update;}void solve() {    N = read(); int mx = 0;    for(int i = 1; i <= N; i++) l[i] = INF, r[i] = 0, tag[i] = 0;     for(int i = 1; i <= N; i++) a[i] = read(), chmax(r[a[i]], i), chmin(l[a[i]], i), chmax;    Build;    LL ans = 0;    for(int i = 1; i <= N; i++) {        q.push({r[a[i]], i}); s.insert;        if(r[a[i]] == i)             if(l[a[i]] + 1 <= i) Mem(1, 1, N, l[a[i]] + 1, i);        int mx = 0;        while(!q.empty() && q.top().fi <= i)            Erase.se), q.pop();        if(!s.empty {            auto it = s.end(); it--;            mx = ;        }        if(mx + 1 <= i) ans += Query(1, 1, N, mx + 1, i);    }    cout << ans << 'n';}signed main() {//  Fin;    for(int T = read(); T--; solve;    return 0;}

如果按原题来做,禁止选一个点对答案的影响是极其鬼畜的,不方便统计,所以我们离线倒序处理,先让所有询问的点不能选,然后反过来逐次让某些点可选,这样答案是不减的,而且更优的答案一定包含此次选的点

预处理出$up_{i,j}$表示$(i,j)$往上走最远可到的'.',$down_{i,j}$表示$(i,j)$往下走最远可到的'.'

于是对于某行,我们可以扫一遍求出所有跨越此行的正方形的最大边长

假设当前处理到此行的$[l,r]$,已经求得区间中$up$和$down$的最值

①若区间包含'X'或$left|up-downright|lt r-l$,左端点++

②否则更新答案并右端点++

右端点移动时直接$O(1)$更新最值

左端点移动时用线段树$O(log_2n)$更新最值

整个过程是$O(nlog_2n)$的

所以每次加入一个可选点时,暴力更新这一列的$up,down$,统计这一行的答案并更新

需要访问单点值,所以用ZKW线段树又快又方便

#include<stdio.h>
#define inf 2147483647
char s[2010][2010];
int x[2010],y[2010],up[2010][8010],ans[2010],down[2010][8010],M,m;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void pu(int id,int x){
    up[id][x]=max(up[id][x<<1],up[id][x<<1|1]);
}
void pd(int id,int x){
    down[id][x]=min(down[id][x<<1],down[id][x<<1|1]);
}
int queryu(int id,int s,int t){
    int c=-inf;
    for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){
        if(~s&1)c=max(c,up[id][s^1]);
        if(t&1)c=max(c,up[id][t^1]);
    }
    return c;
}
void modifyu(int id,int p,int v){
    p+=M;
    for(up[id][p]=v;p>>=1;)pu(id,p);
}
int queryd(int id,int s,int t){
    int c=inf;
    for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){
        if(~s&1)c=min(c,down[id][s^1]);
        if(t&1)c=min(c,down[id][t^1]);
    }
    return c;
}
void modifyd(int id,int p,int v){
    p+=M;
    for(down[id][p]=v;p>>=1;)pd(id,p);
}
int getline(int x){
    int l,r,maxy,miny,res;
    res=0;
    for(l=r=1;l<=m;l++){
        if(l>r){
            r++;
            l--;
            continue;
        }
        maxy=queryu(x,l,r);
        miny=queryd(x,l,r);
        while(maxy!=inf&&miny!=-inf&&miny-maxy>=r-l&&r<m){
            res=max(res,r-l+1);
            r++;
            maxy=max(maxy,up[x][r+M]);
            miny=min(miny,down[x][r+M]);
        }
        if(r==m){
            if(maxy!=inf&&miny!=-inf&&miny-maxy>=r-l)res=max(res,r-l+1);
            break;
        }
    }
    return res;
}
int main(){
    int n,q,i,j;
    scanf("%d%d%d",&n,&m,&q);
    for(M=1;M<m+1;M<<=1);
    for(i=1;i<=n;i++)scanf("%s",s[i]+1);
    for(i=1;i<=q;i++){
        scanf("%d%d",x+i,y+i);
        s[x[i]][y[i]]='X';
    }
    for(i=1;i<=m;i++)s[0][i]=s[n+1][i]='X';
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(s[i][j]!='X'){
                if(s[i-1][j]=='X')
                    up[i][j+M]=i;
                else
                    up[i][j+M]=up[i-1][j+M];
            }else
                up[i][j+M]=inf;
        }
    }
    for(i=n;i>0;i--){
        for(j=1;j<=m;j++){
            if(s[i][j]!='X'){
                if(s[i+1][j]=='X')
                    down[i][j+M]=i;
                else
                    down[i][j+M]=down[i+1][j+M];
            }else
                down[i][j+M]=-inf;
        }
    }
    for(i=1;i<=n;i++){
        for(j=M-1;j>0;j--){
            pd(i,j);
            pu(i,j);
        }
    }
    ans[q]=0;
    for(i=1;i<=n;i++)ans[q]=max(ans[q],getline(i));
    for(i=q;i>1;i--){
        s[x[i]][y[i]]='.';
        for(j=x[i];j<=n;j++){
            if(s[j][y[i]]!='X'){
                if(s[j-1][y[i]]=='X')
                    modifyu(j,y[i],j);
                else
                    modifyu(j,y[i],up[j-1][y[i]+M]);
            }
        }
        for(j=x[i];j>0;j--){
            if(s[j][y[i]]!='X'){
                if(s[j+1][y[i]]=='X')
                    modifyd(j,y[i],j);
                else
                    modifyd(j,y[i],down[j+1][y[i]+M]);
            }
        }
        ans[i-1]=max(ans[i],getline(x[i]));
    }
    for(i=1;i<=q;i++)printf("%dn",ans[i]);
}

本文由贝博体育app发布于编程技术,转载请注明出处:洛谷P4065 [JXOI2017]颜色(线段树)

关键词:

上一篇:没有了
下一篇:机器学习Estimator