UVA 11402 – Ahoy, Pirates!(段树)

UVA 11402 – Ahoy, Pirates!(段树)

大家好,又见面了,我是全栈君,今天给大家准备了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账号...

(0)


相关推荐

  • Xilinx原语ODDR的使用

    ODDRisXilinxHDLLanguageTemplate。ODDR:OutputDoubleDataRate(DDR)。在介绍ODDR之前,我们先简单了解一下OLOGIC。OLOGIC块在FPGA内的位置紧挨着IOB,其作用是FPGA通过IOB发送数据到器件外部的专用同步块。OLOGIC资源的类型有OLOGIC2(位于HPI/Obanks)和OLOGIC3(位于…

  • VMware安装centos7(电动卷闸门安装方法及步骤)

    原文:https://www.jianshu.com/p/ce08cdbc4ddb?utm_source=tuicool&utm_medium=referral本篇文章主要介绍了VMware安装Centos7超详细过程(图文),具有一定的参考价值,感兴趣的小伙伴们可以参考一下1.软硬件准备软件:推荐使用VMwear,我用的是VMwear12镜像:CentOS7,如…

  • Java进阶(二十三)java中long类型转换为int类型

    Java进阶(二十三)java中long类型转换为int类型java中long类型转换为int类型由int类型转换为long类型是向上转换,可以直接进行隐式转换,但由long类型转换为int类型是向下转换,可能会出现数据溢出情况:主要以下几种转换方法,供参考:一、强制类型转换[java]longll=300000;intii=(int)ll;二、调用intValue()方法[j

  • Navigator对象,获取浏览器类型userAgent,机器类型platform

    Navigator对象,获取浏览器类型userAgent,机器类型platformJavaScript常用事件集合,前端小白必备(写的很详细,建议收藏)1.文档加载事件鼠标事件获取浏览器类型,手机机型(容易出问题的地方)事件冒泡与事件委托(面试重点)一、获取浏览器类型letuserAgent=navigator.userAgent;console.log(userAgent);if(userAgent.indexOf(“Opera”)>-1){ //判断是否是Opera浏览器console.log(“Opera”);};

  • vue2.0项目中使用Ueditor富文本编辑器示例

    vue2.0项目中使用Ueditor富文本编辑器示例

    2021年10月11日
  • Linux上端口开放常用命令[通俗易懂]

    Linux上端口开放常用命令[通俗易懂]场景系统部署在linux服务器后常需要开发指定的端口。在linux怎样对端口进行操作。注:博客:https://blog.csdn.net/badao_liumang_qizhi关注公众号霸道的程序猿获取编程相关电子书、教程推送与免费下载。实现#查看想开的端口是否已开:firewall-cmd–query-port=8888/tcp#添加指定需要开放的端口:firewall-cmd–add-port=8888/tcp–permanent#重载入添加的端口:

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号