Skip to content

14172: 【原4172】rose

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4172

Description

“玫瑰的红，容易受伤的梦。”

小R同学与小L同学一起去了日本玩耍，她们在一条路上看到了许许多多的红玫瑰，有些玫瑰还在开放，而另一些已经凋谢。好奇的小L想知道某个区间$$[l,r]$$中最多有多少连续的盛开的玫瑰，但调皮的小R要捣乱。她有一种神奇的药水，可以使凋谢的玫瑰立即重新开放，也可以使开放的玫瑰立即枯萎，甚至可以对同一株玫瑰反复使用。小L很生气，找到了你，希望你帮忙应对小R的捣乱。

给出一个01序列和以下三个操作：

$$1\ l\ r\ x$$： 将区间$$[l, r]$$内的所有数变为$$x$$，$$x$$的取值只可能为0或1；

$$2\ l\ r$$： 查询区间$$[l, r]$$内有多少个1；

$$3\ l\ r$$： 查询区间$$[l, r]$$内最长的连续1的数量。

Input Format

输入共m+2行。第一行为2个正整数n和m，n为01序列的长度，m为操作个数；

第二行为n个用空格隔开的数，只可能为0或1；

第三行至第m+2行为m个操作，格式参照问题描述。

Output Format

对于每一个查询操作，输出一行结果。格式见输入输出样例。

Sample Input

8 3
1 1 0 0 1 0 1 0
2 3 5
1 3 7 1
3 2 8

Sample Output

1
6

数据规模与约定

对于100%的数据，$$1\le n, m\le 10^6$$，$$1\le l \le r\le n$$。

Neight99's solution 

#include <cmath>
#include <iostream>

using namespace std;

const int maxN = 1e6 + 100;

bool roses[maxN] = {0};

class segmentTree {
   private:
    struct Node {
        int l;
        int r;
        int lMax;
        int rMax;
        int mMax;
        int amount;
        int add;

        Node() : l(0), r(0), lMax(0), rMax(0), mMax(0), amount(0), add(0) {}
    };
    Node *data;
    int length;

    void buildTree(int X, int l, int r);
    void update(int X, int l, int r, bool c);
    void pushUp(int X);
    void pushDown(int X);
    int searchMany(int X, int l, int r);
    int searchLongest(int X, int l, int r);

   public:
    segmentTree(int l = maxN) : length(l) { data = new Node[length * 4 + 100]; }
    ~segmentTree() { delete[] data; }

    void buildTree(int n);
    void update(int l, int r, bool c);
    int searchMany(int l, int r);
    int searchLongest(int l, int r);
};

void segmentTree::pushUp(int X) {
    int leftSon = 2 * X, rightSon = 2 * X + 1,
        leftLength = data[leftSon].r - data[leftSon].l + 1,
        rightLength = data[rightSon].r - data[rightSon].l + 1;

    data[X].lMax = data[leftSon].lMax;
    data[X].rMax = data[rightSon].rMax;
    if (data[X].lMax == leftLength) {
        data[X].lMax += data[rightSon].lMax;
    }
    if (data[X].rMax == rightLength) {
        data[X].rMax += data[leftSon].rMax;
    }
    data[X].amount = data[leftSon].amount + data[rightSon].amount;
    data[X].mMax =
        max(max(data[leftSon].rMax + data[rightSon].lMax, data[leftSon].mMax),
            data[rightSon].mMax);
}

void segmentTree::pushDown(int X) {
    int leftSon = 2 * X, rightSon = 2 * X + 1;
    if (data[X].add == 0) {
        return;
    } else if (data[X].l != data[X].r) {
        int add = data[X].add;
        data[leftSon].add = data[rightSon].add = add;
        if (add == 1) {
            data[leftSon].lMax = data[leftSon].rMax = data[leftSon].amount =
                data[leftSon].mMax = 0;
            data[rightSon].lMax = data[rightSon].rMax = data[rightSon].amount =
                data[rightSon].mMax = 0;
        } else if (add == 2) {
            data[leftSon].lMax = data[leftSon].rMax = data[leftSon].amount =
                data[leftSon].mMax = data[leftSon].r - data[leftSon].l + 1;
            data[rightSon].lMax = data[rightSon].rMax = data[rightSon].amount =
                data[rightSon].mMax = data[rightSon].r - data[rightSon].l + 1;
        }
        data[X].add = 0;
    }
}

void segmentTree::buildTree(int n) { buildTree(1, 1, n); }

void segmentTree::buildTree(int X, int l, int r) {
    data[X].add = 0;
    data[X].l = l;
    data[X].r = r;
    if (l == r) {
        data[X].lMax = roses[l];
        data[X].rMax = roses[l];
        data[X].mMax = roses[l];
        data[X].amount = roses[l];
        return;
    }
    int mid = (l + r) >> 1;
    buildTree(2 * X, l, mid);
    buildTree(2 * X + 1, mid + 1, r);
    pushUp(X);
}

void segmentTree::update(int l, int r, bool c) { update(1, l, r, c); }

void segmentTree::update(int X, int l, int r, bool c) {
    if (l <= data[X].l && r >= data[X].r) {
        if (c == 0) {
            data[X].lMax = data[X].mMax = data[X].rMax = data[X].amount = 0;
        } else {
            data[X].lMax = data[X].mMax = data[X].rMax = data[X].amount =
                data[X].r - data[X].l + 1;
        }

        data[X].add = c + 1;
    } else {
        int mid = (data[X].l + data[X].r) >> 1;
        pushDown(X);

        if (l <= mid) {
            update(2 * X, l, r, c);
        }
        if (r > mid) {
            update(2 * X + 1, l, r, c);
        }

        pushUp(X);
    }
}

int segmentTree::searchMany(int l, int r) { return searchMany(1, l, r); }

int segmentTree::searchMany(int X, int l, int r) {
    if (data[X].l > r || data[X].r < l) {
        return 0;
    } else if (l <= data[X].l && data[X].r <= r) {
        return data[X].amount;
    } else {
        int mid = (data[X].l + data[X].r) >> 1;

        pushDown(X);

        int ans = 0;

        return searchMany(2 * X, l, r) + searchMany(2 * X + 1, l, r);
    }
}

int segmentTree::searchLongest(int l, int r) { return searchLongest(1, l, r); }

int segmentTree::searchLongest(int X, int l, int r) {
    if (data[X].l > r || data[X].r < l) {
        return 0;
    } else if (data[X].l >= l && data[X].r <= r) {
        return data[X].mMax;
    } else {
        if (data[X].add != 0) {
            pushDown(X);
        }
        int mid = (data[X].l + data[X].r) >> 1;

        if (r <= mid) {
            return searchLongest(2 * X, l, r);
        } else if (l > mid) {
            return searchLongest(2 * X + 1, l, r);
        } else {
            int left1 = searchLongest(2 * X, l, r),
                right1 = searchLongest(2 * X + 1, l, r);
            int leftRight = data[2 * X].rMax, rightLeft = data[2 * X + 1].lMax;
            if (leftRight > mid - l + 1) {
                leftRight = mid - l + 1;
            }
            if (rightLeft > r - mid) {
                rightLeft = r - mid;
            }

            return max(max(left1, right1), (leftRight + rightLeft));
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    segmentTree smt;

    for (int i = 1; i < n + 1; i++) {
        cin >> roses[i];
    }

    smt.buildTree(n);

    for (int i = 0; i < m; i++) {
        int order, l, r, x, ans;
        cin >> order;
        switch (order) {
            case 1:
                cin >> l >> r >> x;
                smt.update(l, r, x);
                break;
            case 3:
                cin >> l >> r;
                ans = smt.searchLongest(l, r);
                cout << ans << '\n';
                break;
            case 2:
                cin >> l >> r;
                ans = smt.searchMany(l, r);
                cout << ans << '\n';
                break;
        }
    }

    return 0;
}

WashSwang's solution 

#include <iostream>
using namespace std;
const int MAXN=1000001;
int a[MAXN],ans[4*MAXN],tag[4*MAXN],leftc[4*MAXN],rightc[4*MAXN],c[4*MAXN];
inline int ls(int p) {
    return p<<1;
}

inline int rs(int p) {
    return p<<1|1;
}

inline void push_up(int p,int l,int r) {
    int mid=(l+r)>>1;
    ans[p]=ans[ls(p)]+ans[rs(p)];
    leftc[p]=leftc[ls(p)];
    rightc[p]=rightc[rs(p)];
    if (mid-l+1==leftc[ls(p)]) leftc[p]+=leftc[rs(p)];
    if (r-mid==rightc[rs(p)]) rightc[p]+=rightc[ls(p)];
    c[p]=max(max(c[ls(p)],c[rs(p)]),rightc[ls(p)]+leftc[rs(p)]);
}

void build(int l,int r,int p) {
    if (l==r)
    {
        ans[p]=a[l];
        leftc[p]=a[l];
        rightc[p]=a[l];
        c[p]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(p));
    build(mid+1,r,rs(p));
    push_up(p,l,r);
}
inline void add_tag(int p,int l,int r,int k)
{
    tag[p]=k;
    if (k==1)
        ans[p]=leftc[p]=rightc[p]=c[p]=0;
    if (k==2)
        ans[p]=leftc[p]=rightc[p]=c[p]=r-l+1;
}

inline void push_down(int p,int l,int r)
{
    int mid=(l+r)>>1;
    add_tag(ls(p),l,mid,tag[p]);
    add_tag(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}

void update(int nl,int nr,int l,int r,int p,int k)
{
    if (nl<=l&&r<=nr)
    {
        add_tag(p,l,r,k);
        return;
    }
    if (tag[p]!=0) push_down(p,l,r);
    int mid=(l+r)>>1;
    if (nl<=mid) update(nl,nr,l,mid,ls(p),k);
    if (nr>mid) update(nl,nr,mid+1,r,rs(p),k);
    push_up(p,l,r);
}

int query(int nl,int nr,int l,int r,int p)
{
    if (nl<=l&&r<=nr) return ans[p];
    if (tag[p]!=0) push_down(p,l,r);
    int mid=(l+r)>>1,sum=0;
    if (nl<=mid) sum+=query(nl,nr,l,mid,ls(p));
    if (nr>mid) sum+=query(nl,nr,mid+1,r,rs(p));
    return sum;
}

int query2(int nl,int nr,int l,int r,int p)
{
    if (nl<=l&&r<=nr) return c[p];
    int mid=(l+r)>>1,leap=0,lmax=0,rmax=0;
    if (tag[p]!=0) push_down(p,l,r);
    if (mid>=nl) lmax=query2(nl,nr,l,mid,ls(p));
    if (mid<nr) rmax=query2(nl,nr,mid+1,r,rs(p));
    leap=min(mid-nl+1,rightc[ls(p)])+min(nr-mid,leftc[rs(p)]);
    return max(max(lmax,rmax),leap);
}

int m,n,x,k,l,r;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    build(1,n,1);
    for (int i=0;i<m;++i){
        scanf("%d%d%d",&k,&l,&r);
        if (k==1){
            scanf("%d",&x);
            update(l,r,1,n,1,x+1);
        }
        if (k==2)
            printf("%d\n",query(l,r,1,n,1));
        if (k==3)
            printf("%d\n",query2(l,r,1,n,1));
    }
    return 0;
}