codeforces - 145E

Posted by WildCow on March 22, 2018

Lucky Queries

Time Limit: 3000MS
Memory Limit: 256 megabytes

Description

outputstandard output Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya brought home string s with the length of n. The string only consists of lucky digits. The digits are numbered from the left to the right starting with 1. Now Petya should execute m queries of the following form:

  • switch l r — “switch” digits (i.e. replace them with their opposites) at all positions with indexes from l to r, inclusive: each digit 4 is replaced with 7 and each digit 7 is replaced with 4 (1 ≤ l ≤ r ≤ n);
  • count — find and print on the screen the length of the longest non-decreasing subsequence of string s. Subsequence of a string s is a string that can be obtained from s by removing zero or more of its elements. A string is called non-decreasing if each successive digit is not less than the previous one.

Help Petya process the requests.

Input

he first line contains two integers n and m (1 ≤ n ≤ 10^6, 1 ≤ m ≤ 3·10^5) — the length of the string s and the number of queries correspondingly. The second line contains n lucky digits without spaces — Petya’s initial string. Next m lines contain queries in the form described in the statement.

Output

For each query count print an answer on a single line.

Sample Input

3 5
747
count
switch 1 1
count
switch 1 3
count

Sample Output

2
3
2


彻底沦为数据结构解题博客= =!

给你一个只由 4 7 组成的序列
两种操作
第一先选择一个区间,将区间内 4 变成 7, 7 变成 4
第二计算全区间有多少个不递减子序列

然后因为是不递减子序列
所以蛮简单的
不用考虑复杂的区间合并 = =!

维护每个节点区间内 4 - 4, 7 - 7, 4 - 7, 7 - 4 的个数
遇见交换就把 4 - 4 与 7 - 7 的个数,以及 4 - 7 与 7 - 4 的个数交换
最后询问的时候
输出 max(max(tree[1].a01, tree[1].a00), tree[1].a11)
就好了

总感觉有一些部分写得不太优雅


#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;

struct Tree
{
    int l;
    int r;
    bool lazy;
    int a01;
    int a10;
    int a00;
    int a11;
};

Tree tree[N << 2];
int n, m;
char ma[N];

void up(int x)
{
    tree[x].a00 = tree[x << 1].a00 + tree[x << 1 | 1].a00;
    tree[x].a11 = tree[x << 1].a11 + tree[x << 1 | 1].a11;
    tree[x].a01 = max(tree[x << 1].a00 + tree[x << 1 | 1].a01, tree[x << 1].a01 + tree[x << 1 | 1].a11);
    tree[x].a01 = max(tree[x].a01, tree[x << 1].a00 + tree[x << 1 | 1].a11);
    tree[x].a10 = max(tree[x << 1].a11 + tree[x << 1 | 1].a10, tree[x << 1].a10 + tree[x << 1 | 1].a00);
    tree[x].a10 = max(tree[x].a10, tree[x << 1].a11 + tree[x << 1 | 1].a00);
}

void down(int x)
{
    int t;

    t = tree[x].lazy;
    if(t){
    	tree[x << 1].lazy = !tree[x << 1].lazy;
	tree[x << 1 | 1].lazy = !tree[x << 1 | 1].lazy;
	swap(tree[x << 1].a01, tree[x << 1].a10);
	swap(tree[x << 1].a11, tree[x << 1].a00);
	swap(tree[x << 1 | 1].a01, tree[x << 1 | 1].a10);
	swap(tree[x << 1 | 1].a11, tree[x << 1 | 1].a00);
    }
    tree[x].lazy = false;
}

void build(int x, int l, int r)
{
    tree[x].l = l;
    tree[x].r = r;
    tree[x].lazy = false;
    if(l == r){
	if(ma[l] == '4'){
	    tree[x].a00 = 1;
       	    tree[x].a01 = tree[x].a10 = tree[x].a11 = 0;
    	}
	else{
	    tree[x].a11 = 1;
	    tree[x].a01 = tree[x].a10 = tree[x].a00 = 0;
	    }
	}
    else{
        int mid;

        mid = l + ((r - l) >> 1);
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
        up(x);
    }
}

void update(int x, int l, int r)
{
    int ll;
    int rr;

    if(l > r){
    	return ;
    }
    ll = tree[x].l;
    rr = tree[x].r;
    if(ll == l && rr == r){
	tree[x].lazy = !tree[x].lazy;
	swap(tree[x].a01, tree[x].a10);
	swap(tree[x].a11, tree[x].a00);
    }
    else{
	int mid;

	down(x);
	mid = ll + ((rr - ll) >> 1);
	update(x << 1, l, min(mid, r));
	update(x << 1 | 1, max(mid + 1, l), r);
	up(x);
    }
}

int main(int argc, char const *argv[])
{
    while(scanf("%d%d", &n, &m) == 2){
	scanf("%s", ma + 1);
	build(1, 1, n);
	for(int i = 0; i < m; i ++){
	    char ops[110];

    	    scanf("%s", ops);
	    if(ops[0] == 'c'){
		printf("%d\n", max(max(tree[1].a01, tree[1].a00), tree[1].a11));
	    }
	    else{
		int l, r;

		scanf("%d%d", &l, &r);
		update(1, l, r);
	    }
//	    for(int i = 1; i <= 10; i ++){
//                printf("x = %d l = %d r = %d 01 = %d 10 = %d 00 = %d 11 = %d lazy = %d\n", i, tree[i].l, tree[i].r, tree[i].a01, tree[i].a10, tree[i].a00, tree[i].a11, tree[i].lazy);
//	    }
	}
    }

    return 0;
}