当前位置:   article > 正文

Codeforces 145 E-Lucky Queries 【线段树】_长度为n只包含0到4

长度为n只包含0到4

题目来源:https://codeforces.com/problemset/problem/145/E
在这里插入图片描述
在这里插入图片描述
★这题把题目意思看错了。。。难度不是特别大~


题意:

给你一个长度为n的 只包含字符4和7 的字符串,有两种操作

  1. 将 l 到 r 区间内的4变成7、7变成4
  2. 输出整个字符串中的 最长不递减子序列的 长度

要注意的是,这里 不是连续的子序列,我就被这里坑了

思路:

分别用 l4 记录 翻转前4的个数 ,l7 记录翻转前7的个数 ,l47 记录翻转前最长不递减序列的长度
至于 r4 r7 r47 记录的都是翻转后的(很明显 l4=r7 ,r4=l7,这题确实不需要这么多数组,但是我懒
再维护一个 lazy 标记是否翻转就ok了

代码:

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=1e6+5;
const int sz=1<<6;
const int inf=2e9;
const int mod=1e9+7;
typedef long long LL;
int n,m;
char s[maxn];
int l4[maxn<<2],r4[maxn<<2];
int l7[maxn<<2],r7[maxn<<2];
int l47[maxn<<2],r47[maxn<<2];
int lazy[maxn<<2];
template<class T>
inline void read(T &x)
{
    char c;x=1;
    while((c=getchar())<'0'||c>'9') if(c=='-') x=-1;
    T res=c-'0';
    while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
    x*=res;
}
void pushup(int k)
{
    l4[k]=l4[k<<1]+l4[k<<1|1];
    l7[k]=l7[k<<1]+l7[k<<1|1];
    r4[k]=r4[k<<1]+r4[k<<1|1];
    r7[k]=r7[k<<1]+r7[k<<1|1];
    int tmp1=l4[k<<1]+max(l7[k<<1|1],l47[k<<1|1]);
    l47[k]=max(tmp1,l47[k<<1]+l7[k<<1|1]);
    int tmp2=l4[k<<1|1]+max(l7[k<<1],r47[k<<1]);
    r47[k]=max(tmp2,r47[k<<1|1]+l7[k<<1]);
}
void pushdown(int k)
{
    if(lazy[k]){
        lazy[k<<1]^=1;
        swap(l4[k<<1],r4[k<<1]);
        swap(l7[k<<1],r7[k<<1]);
        swap(l47[k<<1],r47[k<<1]);
        lazy[k<<1|1]^=1;
        swap(l4[k<<1|1],r4[k<<1|1]);
        swap(l7[k<<1|1],r7[k<<1|1]);
        swap(l47[k<<1|1],r47[k<<1|1]);
        lazy[k]=0;
    }
}
void build(int k,int l,int r)
{
    lazy[k]=0;
    if(l==r){
        if(s[l]-'0'==4){
            l4[k]=r7[k]=1;
            r4[k]=l7[k]=0;
        }
        else{
            l4[k]=r7[k]=0;
            r4[k]=l7[k]=1;
        }
        l47[k]=r47[k]=0;
        return ;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    pushup(k);
}
void update(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y){
        lazy[k]^=1;
        swap(l4[k],r4[k]);
        swap(l7[k],r7[k]);
        swap(l47[k],r47[k]);
        return ;
    }
    pushdown(k);
    int mid=l+r>>1;
    if(mid>=x) update(k<<1,l,mid,x,y);
    if(mid<y) update(k<<1|1,mid+1,r,x,y);
    pushup(k);
}
int main()
{
    read(n);read(m);
    scanf("%s",(s+1));
    build(1,1,n);
    char op[10];
    int l,r;
    while(m--){
        scanf("%s",op);
        if(op[0]=='c'){
            cout<<(max(l4[1],max(l7[1],l47[1])))<<endl;
        }
        else{
            read(l); read(r);
            update(1,1,n,l,r);
        }
//        for(int j=1;j<=15;j++) cout<<(max(l4[j],max(l7[j],l47[j])))<<' ';
//        cout<<endl;
    }
    return 0;
}
//        1 3
//   1 2       3 3
//1 1   2 2
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/75826
推荐阅读
相关标签
  

闽ICP备14008679号