首页 > 代码库 > HDU 3397 Sequence operation
HDU 3397 Sequence operation
题目：下列操作
Change operations:
0 a b change all characters into ‘0‘s in [a , b]
1 a b change all characters into ‘1‘s in [a , b]
2 a b change all ‘0‘s into ‘1‘s and change all ‘1‘s into ‘0‘s in [a, b]
Output operations:
3 a b output the number of ‘1‘s in [a, b]
4 a b output the length of the longest continuous ‘1‘ string in [a , b]
思路： 基础 区间 合并 不过操作比较多， 题目要求查询最长的 1 因为有异或 也要记下最长的 0
#include <iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<cmath>#include<vector>#define N 100050using namespace std;int flag[N * 4], Xor[N * 4], sum[N * 4];int a[N];int lsum[2][N * 4], rsum[2][N * 4], msum[2][N * 4];int max(int x, int y) { return x > y ? x : y;}void pushup(int i, int l, int r) { int mid = (l + r) >> 1; sum[i] = sum[i << 1] + sum[i << 1 | 1]; for (int j = 0; j < 2; ++j) { lsum[j][i] = lsum[j][i << 1]; rsum[j][i] = rsum[j][i << 1 | 1]; if (lsum[j][i] == mid - l + 1) lsum[j][i] += lsum[j][i << 1 | 1]; if (rsum[j][i] == r - mid) rsum[j][i] += rsum[j][i << 1]; msum[j][i] = max(msum[j][i << 1], msum[j][i << 1 | 1]); msum[j][i] = max(msum[j][i], rsum[j][i << 1] + lsum[j][i << 1 | 1]); }}void pushdown(int i, int l, int r) { if (flag[i] != -1) { int mid = (l + r) >> 1; flag[i << 1] = flag[i << 1 | 1] = flag[i]; Xor[i << 1] = Xor[i << 1 | 1] = 0; sum[i << 1] = (mid - l + 1) * flag[i]; sum[i << 1 | 1] = (r - mid) * flag[i]; lsum[flag[i]][i << 1] = rsum[flag[i]][i << 1] = msum[flag[i]][i << 1] = mid - l + 1; lsum[flag[i]][i << 1 | 1] = rsum[flag[i]][i << 1 | 1] = msum[flag[i]][i << 1 | 1] = r - mid; lsum[1 - flag[i]][i << 1] = rsum[1 - flag[i]][i << 1] = msum[1 - flag[i]][i << 1] = 0; lsum[1 - flag[i]][i << 1 | 1] = rsum[1 - flag[i]][i << 1 | 1] = msum[1 - flag[i]][i << 1 | 1] = 0; flag[i] = -1; } if (Xor[i] != 0) { int mid = (l + r) >> 1; Xor[i << 1] ^= 1; Xor[i << 1 | 1] ^= 1; sum[i << 1] = (mid - l + 1) - sum[i << 1]; sum[i << 1 | 1] = (r - mid) - sum[i << 1 | 1]; swap(lsum[0][i << 1], lsum[1][i << 1]); swap(rsum[0][i << 1], rsum[1][i << 1]); swap(msum[0][i << 1], msum[1][i << 1]); swap(lsum[0][i << 1 | 1], lsum[1][i << 1 | 1]); swap(rsum[0][i << 1 | 1], rsum[1][i << 1 | 1]); swap(msum[0][i << 1 | 1], msum[1][i << 1 | 1]); Xor[i] = 0; }}void build(int l, int r, int i) { flag[i] = -1; Xor[i] = 0; if (l == r) { sum[i] = flag[i] = a[l]; msum[a[l]][i] = rsum[a[l]][i] = lsum[a[l]][i] = 1; msum[1 - a[l]][i] = rsum[1 - a[l]][i] = lsum[1 - a[l]][i] = 0; return; } int mid = (l + r) >> 1; build(l, mid, i << 1); build(mid + 1, r, i << 1 | 1); pushup(i, l, r);}void update(int l, int r, int pl, int pr, int type, int i) { if (l >= pl && r <= pr) { if (type == 0) { flag[i] = 0; sum[i] = 0; Xor[i] = 0; lsum[0][i] = rsum[0][i] = msum[0][i] = r - l + 1; lsum[1][i] = rsum[1][i] = msum[1][i] = 0; return; } if (type == 1) { flag[i] = 1; sum[i] = (r-l+1); Xor[i] = 0; lsum[0][i] = rsum[0][i] = msum[0][i] = 0; lsum[1][i] = rsum[1][i] = msum[1][i] = r-l+1; return; } if(type==2) { Xor[i]^=1; sum[i]=(r-l+1)-sum[i]; swap(lsum[0][i],lsum[1][i]); swap(rsum[0][i],rsum[1][i]); swap(msum[0][i],msum[1][i]); return; } return; } pushdown(i,l,r); int mid=(l+r)>>1; if(pl<=mid)update(l,mid,pl,pr,type,i<<1); if(pr>mid)update(mid+1,r,pl,pr,type,i<<1|1); pushup(i,l,r);}int query1(int l,int r,int pl,int pr,int i){ if(l>=pl&&r<=pr) return sum[i]; pushdown(i,l,r); int mid=(l+r)>>1; int tmp=0; if(pl<=mid)tmp+=query1(l,mid,pl,pr,i<<1); if(pr>mid)tmp+=query1(mid+1,r,pl,pr,i<<1|1); pushup(i,l,r); return tmp;}int query2(int l,int r,int pl,int pr,int i){ if(l>=pl&&r<=pr) { return msum[1][i]; } pushdown(i,l,r); int mid=(l+r)>>1; if(pr<=mid)return query2(l,mid,pl,pr,i<<1); else if(pl>mid)return query2(mid+1,r,pl,pr,i<<1|1); else { int tmp=0; if(mid-rsum[1][i<<1]+1>=pl) tmp+=rsum[1][i<<1]; else tmp+=mid-pl+1; if(mid+lsum[1][i<<1|1]<=pr) tmp+=lsum[1][i<<1|1]; else tmp+=pr-mid; int maxn1=query2(l,mid,pl,mid,i<<1); int maxn2=query2(mid+1,r,mid+1,pr,i<<1|1); tmp=max(tmp,maxn1); tmp=max(tmp,maxn2); return tmp; }}int main() { int n,m,tt; scanf("%d",&tt); while(tt--) { scanf("%d%d",&n,&m); for(int i=0;i<n;++i) scanf("%d",&a[i]); n--; build(0,n,1); while(m--) { int x,y,z; scanf("%d%d%d",&z,&x,&y); if(z<=2)update(0,n,x,y,z,1); else if(z==3) { printf("%d\n",query1(0,n,x,y,1)); } else printf("%d\n",query2(0,n,x,y,1)); } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。