codeforces 145 E. Lucky Queries (线段树lazy标记)

Posted by 111qqz on Tuesday, September 27, 2016

TOC

题目链接

题意:给出一串只由数字'4'和'7'组成的串。两种操作,一种是询问整个串中最长非下降子序列的长度,另一种给出区间[l,r],将区间中的没个数反转,反转的定义为,4变成7,7变成4.

思路:线段树lazy标记。

线段树的域记录5个信息,c4,c7,c47,c74,flip,a分别表示4的个数,7的个数,非下降子序列的个数,非上升的子序列的个数,以及该区间是否被翻转。

纠结了很久PushUp操作。。。。

c4和c7倒是没什么疑问。。。。

一开始觉得c47是由三部分的最大值更新得到的。。。

left.c4+right.c47,left.c4+right.c7,left.c47+right.c7…

但是样例过不了。。。

纠结了半天发现。。。

比如4774,4444是左右两个区间的时候。。。。

c47最大是5.。。但是left.c4 + right.c7=6,比正确答案大。

原因是。。一个区间中4的位置可能是分散的。。。这样只有某段连续出现的4对答案的贡献是正确的。。。

所以只有区间长度为1的时候c4+c7的更新方式才是合法的。。。

我们不妨在初始化的时候。。。。在线段树的叶子节点直接设置c47为1(当然相应地c74也要为1)

另外一个收获是。。。线段树对于区间的操作(对于点的操作也是同样)

不一定是某种常见的定义过的操作(求和啊,最大值最小值啊之类的)

也可能是某种自定义的操作。。。

比如这道题中的flip操作。。。

就是对区间的一个自定义的操作。。。

/* ***********************************************
Author :111qqz
Created Time :Tue 27 Sep 2016 09:14:22 AM CST
File Name :code/cf/problem/145E.cpp
 ************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N = 1E6+7;
int n,m;
char st[N];
struct node
{
    int c7,c4,c47,c74;
    bool flip;
    void out()
    {
    printf("c4:%d c7: %d c47 :%d c74 : %d\n",c4,c7,c47,c74);
    }
}tree[N<<2];
void PushUp( int rt)
{
    tree[rt].c4 = tree[rt<<1].c4 + tree[rt<<1|1].c4;
    tree[rt].c7 = tree[rt<<1].c7 + tree[rt<<1|1].c7;
    tree[rt].c47 = max(tree[rt<<1].c4 + tree[rt<<1|1].c47 , tree[rt<<1].c47 + tree[rt<<1|1].c7);
    tree[rt].c74 = max(tree[rt<<1].c7 + tree[rt<<1|1].c74, tree[rt<<1].c74 + tree[rt<<1|1].c4);
}
void build( int l,int r ,int rt)
{
    if (l==r)
    {
    if (st[l-1]=='4') tree[rt].c4 = 1;
    else tree[rt].c7 = 1;
    tree[rt].c47 = tree[rt].c74 = 1;
    return;
    }
    int m = (l+r)>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}
void Flip( int rt)
{
    tree[rt].flip^=1;
    swap(tree[rt].c4,tree[rt].c7);
    swap(tree[rt].c47,tree[rt].c74);
}
void PushDown( int rt)
{
    if (tree[rt].flip)
    {
    Flip(rt<<1);
    Flip(rt<<1|1);
    tree[rt].flip = 0 ;
    }
}
void update(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R)
    {
    Flip(rt);
    return;
    }
    PushDown(rt);
    int m = (l+r)>>1;
    if (L<=m) update(L,R,lson);
    if (R>=m+1)  update(L,R,rson);
    PushUp(rt);
}
int main()
{
#ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    scanf("%s",st);
    build(1,n,1);
    while (m--)
    {
    char opt[10];
    scanf("%s",opt);
    //  cout<<"opt:"<<opt<<endl;
    if (opt[0]=='c')
    {
        printf("%d\n",tree[1].c47);
    }
    else
    {
        int x,y;
        scanf("%d%d",&x,&y);
        update(x,y,1,n,1);
    }
    }
#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付