C++(clang++ 11.0.1) 解法, 执行用时: 173ms, 内存消耗: 10572K, 提交时间: 2023-04-06 17:27:06
#include <iostream>
#include <cstring>
using namespace std;
using i64 = long long;
const int N = 100010;
struct Node {
int l, r;
int ls[2], ms[2], rs[2];
bool rev;
} tr[N << 2];
int n, m;
int w[N];
void pushup(Node& u, const Node& l, const Node& r) {
for (int i : {0, 1}) {
u.ms[i] = max(l.ms[i], r.ms[i]);
u.ms[i] = max(u.ms[i], l.rs[i] + r.ls[i]);
u.ls[i] = l.ls[i];
if (u.ls[i] == l.r - l.l + 1) u.ls[i] += r.ls[i];
u.rs[i] = r.rs[i];
if (u.rs[i] == r.r - r.l + 1) u.rs[i] += l.rs[i];
}
}
void pushup(int u) {
pushup(tr[u], tr[u << 1], tr[u << 1 |1]);
}
void pushrev(int u) {
tr[u].rev ^= 1;
swap(tr[u].ms[0], tr[u].ms[1]);
swap(tr[u].ls[0], tr[u].ls[1]);
swap(tr[u].rs[0], tr[u].rs[1]);
}
void pushdown(int u) {
if (tr[u].rev) {
pushrev(u << 1);
pushrev(u << 1 | 1);
tr[u].rev = 0;
}
}
void build(int u, int l, int r) {
tr[u] = {l, r};
if (l == r) {
int v = w[l];
tr[u].ms[v] = tr[u].ls[v] = tr[u].rs[v] = 1;
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return pushrev(u);
int mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
if (l <= mid) modify(u << 1, l, r);
if (r > mid) modify(u << 1 | 1, l, r);
pushup(u);
}
Node query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
if (r <= mid) return query(u << 1, l, r);
if (l > mid) return query(u << 1 | 1, l, r);
Node res;
pushup(res, query(u << 1, l, r), query(u << 1 | 1, l, r));
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
build(1, 1, n);
cin >> m;
while (m--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) modify(1, l, r);
else cout << query(1, l, r).ms[1] << '\n';
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 446ms, 内存消耗: 11740K, 提交时间: 2019-07-19 23:58:52
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls x<<1
#define rs x<<1|1
const int N=1e5+100;
int n,m;
struct node
{
int l,r,l1,r1,m1,l0,r0,m0,lzy;
} t[N<<2];
void pushup(int x)
{
t[x].l1=t[ls].l1;
if(t[ls].l1==t[ls].r-t[ls].l+1) t[x].l1+=t[rs].l1;
t[x].r1=t[rs].r1;
if(t[rs].r1==t[rs].r-t[rs].l+1) t[x].r1+=t[ls].r1;
t[x].m1=t[ls].r1+t[rs].l1;
t[x].m1=max(t[x].m1,max(t[ls].m1,t[rs].m1));
t[x].l0=t[ls].l0;
if(t[ls].l0==t[ls].r-t[ls].l+1) t[x].l0+=t[rs].l0;
t[x].r0=t[rs].r0;
if(t[rs].r0==t[rs].r-t[rs].l+1) t[x].r0+=t[ls].r0;
t[x].m0=t[ls].r0+t[rs].l0;
t[x].m0=max(t[x].m0,max(t[ls].m0,t[rs].m0));
}
void pushdown(int x)
{
if(t[x].lzy)
{
t[ls].lzy^=1;
t[rs].lzy^=1;
t[x].lzy^=1;
swap(t[ls].l0,t[ls].l1);
swap(t[ls].r1,t[ls].r0);
swap(t[ls].m0,t[ls].m1);
swap(t[rs].l0,t[rs].l1);
swap(t[rs].r1,t[rs].r0);
swap(t[rs].m0,t[rs].m1);
}
}
void build(int l,int r ,int x)
{
t[x].l=l,t[x].r=r;
if(l==r)
{
int v;
cin>>v;
if(v==1) t[x].l1=t[x].r1=t[x].m1=1;
else t[x].l0=t[x].r0=t[x].m0=1;
return ;
}
int mid=l+r>>1;
build(l,mid,ls);
build(mid+1,r,rs);
pushup(x);
}
void update(int L,int R,int x)
{
int l=t[x].l,r=t[x].r;
if(L<=l&&r<=R)
{
t[x].lzy^=1;
swap(t[x].l0,t[x].l1);
swap(t[x].r1,t[x].r0);
swap(t[x].m0,t[x].m1);
return ;
}
pushdown(x);
int mid=l+r>>1;
if(L<=mid) update(L,R,ls);
if(R>mid)update(L,R,rs);
pushup(x);
}
int query(int L,int R,int x)
{
int l=t[x].l,r=t[x].r;
if(L<=l&&r<=R) return t[x].m1;
pushdown(x);
int mid=l+r>>1;
if(R<=mid) return query(L,R,ls);//ls可以等于mid
if(L>mid) return query(L,R,rs);
int res1=query(L,R,ls);
int res2=query(L,R,rs);
int res3=min(mid-L+1,t[ls].r1)+min(R-mid,t[rs].l1);
return max(res1,max(res2,res3));
}
int main()
{
cin>>n;
build(1,n,1);
cin>>m;
for(int i=1,op,x,y,z;i<=m;i++)
{
cin>>op>>x>>y;
if(op==1)update(x,y,1);
else cout<<query(x,y,1)<<endl;
}
return 0;
}
{0,1}；1 <= x <= y <= n ）
对于op=1，表示对下标属于闭区间[x,y]的战士施放魔法，使她们"叛变";对于op=0，表示询问下标属于闭区间[x,y]的连续最多的白山茶战士的数目。注：此题请不要使用多组输入！