# 14172: 【原4172】rose

### 题目描述

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

## Description

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

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

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

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

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

1
6

## 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;

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;
return;
} else if (data[X].l != data[X].r) {
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;
}
}
}

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

void segmentTree::buildTree(int X, int l, int r) {
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;
}

} 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 {
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;
tag[p]=0;
}

void update(int nl,int nr,int l,int r,int p,int k)
{
if (nl<=l&&r<=nr)
{
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;
}
``````