程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj 1858: [Scoi2010] 序列操作 題解

bzoj 1858: [Scoi2010] 序列操作 題解

編輯:C++入門知識

【原題】

1858: [Scoi2010]序列操作

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1031 Solved: 529
[Submit][Status]

Description

lxhgww最近收到了一個01序列,序列裡面包含了n個數,這些數要麼是0,要麼是1,現在對於這個序列有五種變換操作和詢問操作: 0 a b 把[a, b]區間內的所有數全變成0 1 a b 把[a, b]區間內的所有數全變成1 2 a b 把[a,b]區間內的所有數全部取反,也就是說把所有的0變成1,把所有的1變成0 3 a b 詢問[a, b]區間內總共有多少個1 4 a b 詢問[a, b]區間內最多有多少個連續的1 對於每一種詢問操作,lxhgww都需要給出回答,聰明的程序員們,你們能幫助他嗎?

Input

輸入數據第一行包括2個數,n和m,分別表示序列的長度和操作數目 第二行包括n個數,表示序列的初始狀態 接下來m行,每行3個數,op, a, b,(0<=op<=4,0<=a<=b

Output

對於每一個詢問操作,輸出一行,包括1個數,表示其對應的答案

Sample Input

10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

Sample Output

5
2
6
5

HINT

對於30%的數據,1<=n, m<=1000
對於100%的數據,1<=n, m<=100000

Source

Day2

【分析】真是一道猥瑣的線段樹的題目。以前我沒寫過染色等題目,但是還是YY出了譬如最大連續段數的求法。在線段樹中還是要記錄一下區間左端點數碼、右端點數碼。後來我越想越復雜,還要記錄左(和右)端點如果是1(和0),最長的連續的個數。因為在L~R由L~M和M+1~R轉移的時候,最長連續1的個數可能是左區間右端點連續的1和右區間左端點連續的1合並造成的。

此外,其實還是要記錄最長連續0的個數,因為要區間取反的。

先挖個坑,以後有空的話再詳細的寫一下算法。

【代碼】

#include
#include
#define N 100005
#define LL a[L].r-a[L].l+1
#define RR a[R].r-a[R].l+1
#define PP a[P].r-a[P].l+1
#define mid ((a[k].l+a[k].r)>>1)
using namespace std;
struct Tree
{
  int l,r,lnum,rnum,l1,r1,l0,r0,cover,num,max0,max1;
}a[N*3];
int data[N],x,y,opt,temp,n,i,Q;
inline void up(int k)
{
  int L=k<<1,R=k<<1|1;
  a[k].lnum=a[L].lnum;a[k].rnum=a[R].rnum;
  a[k].l1=a[L].l1;if (a[L].l1==LL) a[k].l1+=a[R].l1;
  a[k].r1=a[R].r1;if (a[R].r1==RR) a[k].r1+=a[L].r1;
  a[k].l0=a[L].l0;if (a[L].l0==LL) a[k].l0+=a[R].l0;
  a[k].r0=a[R].r0;if (a[R].r0==RR) a[k].r0+=a[L].r0;
  a[k].num=a[L].num+a[R].num;
  a[k].max1=max(a[L].max1,a[R].max1);
  if (a[L].rnum&a[R].lnum) a[k].max1=max(a[k].max1,a[L].r1+a[R].l1);
  a[k].max0=max(a[L].max0,a[R].max0);
  if ((!a[L].rnum)&(!a[R].lnum)) a[k].max0=max(a[k].max0,a[L].r0+a[R].l0);
}
inline void build(int k,int l,int r)
{
  a[k].l=l;a[k].r=r;
  if (l==r) 
  {
    a[k].lnum=a[k].rnum=a[k].l1=a[k].r1=a[k].num=a[k].max1=data[l];
    a[k].l0=a[k].r0=a[k].max0=data[l]^1;return;
  }
  build(k<<1,l,mid);
  build(k<<1|1,mid+1,r);
  up(k);
}
inline void update(int P,int add)
{
  if (add==1)
  {
    a[P].l1=a[P].r1=a[P].num=a[P].max1=PP;
    a[P].l0=a[P].r0=a[P].max0=0;
    a[P].lnum=a[P].rnum=1;
  }
  if (add==-1)
  {
    a[P].l1=a[P].r1=a[P].num=a[P].max1=a[P].lnum=a[P].rnum=0;
    a[P].l0=a[P].r0=a[P].max0=PP;
  }
  if (add==2)
  {
  swap(a[P].l0,a[P].l1);swap(a[P].r0,a[P].r1);swap(a[P].max0,a[P].max1);
    a[P].lnum^=1;a[P].rnum^=1;
    a[P].num=PP-a[P].num;
  }
}
inline void down(int k,int P)
{
  update(P,temp=a[k].cover);
  if (temp&1) a[P].cover=temp;
  if (temp==2)
  {
    if (a[P].cover&1) a[P].cover=-a[P].cover;
    else a[P].cover=2-a[P].cover;
  }
}
void work(int k)
{
  if (x<=a[k].l&&a[k].r<=y)
  {
    update(k,opt);
    if (!a[k].cover) a[k].cover=opt;
    else a[k].cover=(opt&1)?opt:((a[k].cover==2)?0:-a[k].cover);
    return;
  }
  down(k,k<<1);down(k,k<<1|1);a[k].cover=0;
  if (x<=mid) work(k<<1);
  if (y>mid) work(k<<1|1);
  up(k);
}
int ask(int k)
{
  if (x<=a[k].l&&a[k].r<=y) return (opt==3)?a[k].num:a[k].max1;
  down(k,k<<1);down(k,k<<1|1);a[k].cover=0;
  int Mid=(a[k].l+a[k].r)>>1;
  if (opt==3) return (((x<=Mid)?ask(k<<1):0)+((y>Mid)?ask(k<<1|1):0));
  int Max=0;
  if (x<=Mid) Max=max(Max,ask(k<<1));
  if (y>Mid) Max=max(Max,ask(k<<1|1));
  if (x<=Mid&&y>Mid) Max=max(Max,min(a[k<<1].r1,Mid-x+1)+min(a[k<<1|1].l1,y-Mid));
  return Max;
}
inline int c(int k) {return (!k)?-1:k;}
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
        }return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
int main()
{
  read(n);read(Q);
  for (i=1;i<=n;i++) read(data[i]);
  build(1,1,n);
  while (Q--)
  {
    read(opt);read(x);x++;read(y);y++;
    if (opt<3) opt=c(opt),work(1);
    else printf("%d\n",ask(1));
  }
  return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved