A simple Blog for wyx I've been down the bottle hoping.
BZOJ 4826: [Hnoi2017]影魔 线段树 离线 扫描线
发表于: | 分类: Oi | 评论:0 | 阅读:76

我们先来分析一下题吧 = =

首先看到最大值最小值我们枚举一下嘛 ……

从大到小枚举一下最大值,然后我们得到每个权值的控制区间,考虑区间左右两个数字必然是第一个比他大的数字,假设位置分别是 $L,R$ 最大值所在位置是 $pos$

然后……然后讨论一下嘛,$(L,R)$ 显然是 $p_1$ 的贡献,然后 $(L+1\dots pos-1,R)$ 和 $(L,pos+1\dots R-1)$ 显然都是$p_2$的贡献

然后我们把一个左端点当成一维坐标,一个右端点当成另外一维= =

然后一次操作对应着两台直线的加法和一个单点修改

然后树套树,分别维护两种形式的直线

然后RE

然后调内存

MLE了= =

嘿嘿嘿两个线段树串行吧

$2\times 10^5$ Tle了

日……

先放个Tle代码帮助理解一下,正解在下面

#include <set>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200000+5;
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int n;

struct seg {
    int tmp[N*90], ls[N*90], rs[N*90], lazy[N*90], sz, root[N<<2];

    inline void down(int k,int l,int r) {
        if(!lazy[k] || l==r) return;
        int mid = (l+r) >> 1, tt = lazy[k]; lazy[k] = 0;
        if(!ls[k]) ls[k] = ++sz;
        if(!rs[k]) rs[k] = ++sz;
        lazy[ls[k]] += tt;
        lazy[rs[k]] += tt;
        tmp[ls[k]] += (mid-l+1)*tt;
        tmp[rs[k]] += (r-mid)*tt;
    }

    inline void change1(int &k,int l,int r,int x,int y,int val) {
        if(!k) k = ++sz;
        if(l==x && r==y) {
            tmp[k] += (r-l+1) * val;
            lazy[k] += val;
            return;
        }
        down(k,l,r);
        int mid = (l+r) >> 1;
        if(y <= mid) change1(ls[k],l,mid,x,y,val);
        else if(x > mid) change1(rs[k],mid+1,r,x,y,val);
        else change1(ls[k],l,mid,x,mid,val), change1(rs[k],mid+1,r,mid+1,y,val);
        tmp[k] = tmp[ls[k]] + tmp[rs[k]];
    }

    inline int ask1(int k,int l,int r,int x,int y) {
        if(!k) return 0;
        if(l==x && r==y) return tmp[k];
        down(k,l,r);
        int mid = (l+r) >> 1;
        if(y <= mid) return ask1(ls[k],l,mid,x,y);
        else if(x > mid) return ask1(rs[k],mid+1,r,x,y);
        else return ask1(ls[k],l,mid,x,mid) + ask1(rs[k],mid+1,r,mid+1,y) ;
    }

    inline void change(int k,int l,int r,int x1,int x2,int y,int val) {
        change1(root[k],1,n,x1,x2,val);
        if(l==r) return;
        int mid = (l+r) >> 1;
        if(y<=mid) change(k<<1,l,mid,x1,x2,y,val);
        else change(k<<1|1,mid+1,r,x1,x2,y,val);
    }

    inline int ask(int k,int l,int r,int x1,int y1,int x2,int y2) {
        if(l==y1 && r==y2) return ask1(root[k],1,n,x1,x2);
        int mid = (l+r) >> 1;
        if(y2 <= mid) return ask(k<<1,l,mid,x1,y1,x2,y2);
        else if(y1 > mid) return ask(k<<1|1,mid+1,r,x1,y1,x2,y2);
        else return ask(k<<1,l,mid,x1,y1,x2,mid) + ask(k<<1|1,mid+1,r,x1,mid+1,x2,y2);
    }

}tr1;

set <int> s;

struct data {
    int pos,val;
    bool operator < (const data &z) const {
        return val > z.val;
    }
} a[N];
    
int L[N], R[N], X[N], Y[N], ans[N];

int main() {
    freopen("tt.in","r",stdin);
    n = read(); int m = read(), p1 = read(), p2 = read();
    for(int i=1;i<=n;++i) a[i].pos = i, a[i].val = read();
    s.insert(0); s.insert(n+1);
    set <int> :: iterator it;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i) {
        int j=i+1;
        while(a[j].val == a[i].val) j ++; 
        j --;
        for(int k=i;k<=j;++k) s.insert(a[k].pos);
        for(int k=i;k<=j;++k) {
            it = s.upper_bound(a[k].pos); R[a[k].pos] = *it;
            it = --s.lower_bound(a[k].pos);L[a[k].pos] = *it;
        }
        for(int k=i;k<=j;++k) {
            bool flag = false;
            if(L[a[k].pos] == 0 && R[a[k].pos] == n+1) continue;
            if(L[a[k].pos] == 0) flag = true;
            if(R[a[k].pos] == n+1) flag = true;
            if(!flag) tr1.change(1,1,n,L[a[k].pos],L[a[k].pos], R[a[k].pos],p1);
            if(L[a[k].pos]+1<=a[k].pos-1 && R[a[k].pos] != n+1)tr1.change(1,1,n,L[a[k].pos]+1,a[k].pos-1,R[a[k].pos],p2);
        }
    }
    for(int i=1;i<n;++i)
        tr1.change(1,1,n,i,i,i+1,p1);
    for(int i=1;i<=m;++i) {
        X[i] = read(), Y[i] = read();
        ans[i] += tr1.ask(1,1,n, X[i], X[i], Y[i], Y[i]);
    }
    for(int i=1;i<=tr1.sz;++i) tr1.tmp[i] = tr1.lazy[i] = tr1.ls[i] = tr1.rs[i] = 0;
    for(int i=1;i<=(n<<2);++i) tr1.root[i] = 0;
    tr1.sz = 0;
    for(int i=1;i<=n;++i) 
        if(a[i].pos+1<=R[a[i].pos]-1 && L[a[i].pos] != 0) tr1.change(1,1,n,a[i].pos+1,R[a[i].pos]-1,L[a[i].pos],p2);
    for(int i=1;i<=m;++i) printf("%d\n", ans[i] + tr1.ask(1,1,n,X[i], X[i], Y[i], Y[i]));
}

好了现在我们可以想方法卡掉这个log了

我们把询问离线下来,然后从上到下扫一下就行了

然后两个log串行,卡掉了一个log = =

然后A了......

#include <set>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL N = 2e5+5;
const LL M = N << 2;
LL tr[M], lazy[M];

inline LL read() {
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

inline void down(LL k,LL l,LL r) {
    if(l==r||!lazy[k]) return;
    LL mid = (l+r) >> 1, tmp = lazy[k]; lazy[k] = 0;
    tr[k<<1] += (mid-l+1) * tmp;
    tr[k<<1|1] += (r-mid) * tmp;
    lazy[k<<1] += tmp;
    lazy[k<<1|1] += tmp;
    return;
}

inline void change(LL k,LL l,LL r,LL x,LL y,LL val) {
    if(l==x && r==y) {
        tr[k] += (r-l+1)*val;
        lazy[k] += val;
        return;
    }
    down(k,l,r);
    LL mid = (l+r) >> 1;
    if(y <= mid) change(k<<1,l,mid,x,y,val);
    else if(x > mid) change(k<<1|1,mid+1,r,x,y,val);
    else change(k<<1,l,mid,x,mid,val), change(k<<1|1,mid+1,r,mid+1,y,val);
    tr[k] = tr[k<<1] + tr[k<<1|1];
}

inline LL ask(LL k,LL l,LL r,LL x,LL y) {
    if(l==x && r==y) return tr[k];
    down(k,l,r);
    LL mid = (l+r) >> 1;
    if(y <= mid) return ask(k<<1,l,mid,x,y);
    else if(x > mid) return ask(k<<1|1,mid+1,r,x,y);
    else return ask(k<<1,l,mid,x,mid) + ask(k<<1|1,mid+1,r,mid+1,y);
}

struct line {
    LL x1,x2,y,val,opt,id;
    bool operator < (const line &z) const {
        if(y != z.y) return y < z.y;
        return opt < z.opt;
    }
} l[N<<4];

set <LL> s;

struct data {
    LL pos,val;
    bool operator < (const data &z) const {
        return val > z.val;
    }
} a[N];
    
LL L[N], R[N], X[N], Y[N], ans[N], top;

int main() {
//  freopen("tt.in","r",stdin);
    LL n = read(); LL m = read(), p1 = read(), p2 = read();
    for(LL i=1;i<=n;++i) a[i].pos = i, a[i].val = read();
    s.insert(0); s.insert(n+1);
    set <LL> :: iterator it;
    sort(a+1,a+n+1);
    for(LL i=1;i<=n;++i) {
        LL j=i+1;
        while(a[j].val == a[i].val) j ++; 
        j --;
        for(LL k=i;k<=j;++k) s.insert(a[k].pos);
        for(LL k=i;k<=j;++k) {
            it = s.upper_bound(a[k].pos); R[a[k].pos] = *it;
            it = --s.lower_bound(a[k].pos);L[a[k].pos] = *it;
        }
        for(LL k=i;k<=j;++k) {
            bool flag = false;
            if(L[a[k].pos] == 0 && R[a[k].pos] == n+1) continue;
            if(L[a[k].pos] == 0) flag = true;
            if(R[a[k].pos] == n+1) flag = true;
            if(!flag) l[++top] = (line){L[a[k].pos],L[a[k].pos], R[a[k].pos],p1,0,0};
            if(L[a[k].pos]+1<=a[k].pos-1 && R[a[k].pos] != n+1) l[++top] = (line){L[a[k].pos]+1, a[k].pos-1, R[a[k].pos], p2, 0, 0};
        }
    }
    for(LL i=1;i<=m;++i) X[i] = read(), Y[i] = read();
    for(LL i=1;i<=m;++i) {
        l[++top] = (line){X[i], Y[i], X[i]-1,0,1,i};
        l[++top] = (line){X[i], Y[i], Y[i] , 0,2,i};
    }
    for(LL i=1;i<n;++i) l[++top] = (line){i,i,i+1,p1,0,0};
    sort(l+1,l+top+1);
    for(LL i=1;i<=top;++i) {
        if(l[i].opt==0) change(1,0,n+1,l[i].x1,l[i].x2,l[i].val);
        else if(l[i].opt==1) ans[l[i].id] -= ask(1,0,n+1,l[i].x1,l[i].x2);
        else ans[l[i].id] += ask(1,0,n+1,l[i].x1,l[i].x2);
    }

    top = 0;
    memset(tr,0,sizeof tr);
    memset(lazy,0,sizeof lazy);
    for(LL i=1;i<=m;++i) {
        l[++top] = (line){X[i], Y[i],X[i]-1, 0, 1, i};
        l[++top] = (line){X[i], Y[i],  Y[i], 0, 2, i};
    }
    for(LL i=1;i<=n;++i) 
        if(a[i].pos+1<=R[a[i].pos]-1 && L[a[i].pos] != 0) l[++top] = (line){a[i].pos+1,R[a[i].pos]-1,L[a[i].pos],p2,0,0};
    sort(l+1,l+top+1);
//  for(LL i=1;i<=top;++i) cout << l[i].x1 << " " << l[i].x2 << " " << l[i].y  << " " << l[i].id << endl; 
    for(LL i=1;i<=top;++i) {
        if(l[i].opt==0) change(1,0,n+1,l[i].x1,l[i].x2,l[i].val);
        else if(l[i].opt==1) ans[l[i].id] -= ask(1,0,n+1,l[i].x1,l[i].x2);
        else ans[l[i].id] += ask(1,0,n+1,l[i].x1,l[i].x2);
    }
    for(LL i=1;i<=m;++i) printf("%lld\n", ans[i]);
}


Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP