大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
UVA 11402 – Ahoy, Pirates!
题意:总的来说意思就是给一个01串,然后有3种操作
1、把一个区间变成1
2、把一个区间变成0
3、把一个区间翻转(0变1,1变0)
思路:线段树搞,开一个延迟标记当前操作就可以,注意几种状态间的转变方式就可以
代码:
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define INF 0x3f3f3f3f#define lson(x) ((x<<1)+1)#define rson(x) ((x<<1)+2)const int N = 1100005;int t, s[N], n, sn;char str[55];struct Node { int l, r, b, flag; Node() {} Node(int l, int r) { this->l = l; this->r = r; b = flag = 0; } int len() { return r - l + 1; }} node[4 * N];void pushup(int x) { node[x].b = node[lson(x)].b + node[rson(x)].b;}void build(int l, int r, int x = 0) { node[x] = Node(l, r); if (l == r) { node[x].b = s[l]; return; } int mid = (node[x].l + node[x].r) / 2; build(l, mid, lson(x)); build(mid + 1, r, rson(x)); pushup(x);}void init() { scanf("%d", &n); sn = 0; while (n--) { int num; scanf("%d", &num); scanf("%s", str); int len = strlen(str); while (num--) { for (int i = 0; i < len; i++) s[sn++] = str[i] - '0'; } } build(0, sn - 1);}//0不变,1黑。2白。3翻转int getS(int a, int b) { if (a == 3 && b == 3) return 0; if (a == 3 && b == 1) return 2; if (a == 3 && b == 2) return 1; if (a == 3 && b == 0) return 3; if (a == 2) return 2; if (a == 1) return 1; return 0;}void pushdown(int x) { if (node[x].flag) { int ls = getS(node[x].flag, node[lson(x)].flag); node[lson(x)].flag = ls; if (node[x].flag == 2) node[lson(x)].b = 0; if (node[x].flag == 1) node[lson(x)].b = node[lson(x)].len(); if (node[x].flag == 3) node[lson(x)].b = node[lson(x)].len() - node[lson(x)].b; int rs = getS(node[x].flag, node[rson(x)].flag); node[rson(x)].flag = rs; if (node[x].flag == 2) node[rson(x)].b = 0; if (node[x].flag == 1) node[rson(x)].b = node[rson(x)].len(); if (node[x].flag == 3) node[rson(x)].b = node[rson(x)].len() - node[rson(x)].b; node[x].flag = 0; }}void set(int l, int r, int v, int x = 0) { if (node[x].l >= l && node[x].r <= r) { int ts = getS(v, node[x].flag); if (v == 1) node[x].b = node[x].len(); else if (v == 2) node[x].b = 0; else node[x].b = node[x].len() - node[x].b; node[x].flag = ts; return; } pushdown(x); int mid = (node[x].l + node[x].r) / 2; if (l <= mid) set(l, r, v, lson(x)); if (r > mid) set(l, r, v, rson(x)); pushup(x);}int S(int l, int r, int x = 0) { if (node[x].l >= l && node[x].r <= r) return node[x].b; int mid = (node[x].l + node[x].r) / 2; int ans = 0; pushdown(x); if (l <= mid) ans += S(l, r, lson(x)); if (r > mid) ans += S(l, r, rson(x)); pushup(x); return ans;}int main() { int cas = 0; scanf("%d", &t); while (t--) { init(); int q; scanf("%d", &q); char Q[5]; int a, b; printf("Case %d:\n", ++cas); int Qcas = 0; while (q--) { scanf("%s%d%d", Q, &a, &b); if (Q[0] == 'F') set(a, b, 1); if (Q[0] == 'E') set(a, b, 2); if (Q[0] == 'I') set(a, b, 3); if (Q[0] == 'S') printf("Q%d: %d\n", ++Qcas, S(a, b)); } } return 0;}
版权声明:本文博主原创文章。博客,未经同意不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116957.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...