1237.数袜子
Time Limit: 2000 MS
Memory Limit: 65536 K
Total Submissions: 428 (101 users)
Accepted: 91 (76 users)
[ My Solution
]
Description
话说当年swgr早上起床时经常在一堆颜色相近但款式不同的袜子堆里找到两只配对的袜子,为此常常要浪费不少时间。久而久之,swgr终于想到了一劳永逸的办法:他买了一大堆一模一样的袜子,这样就不用担心配对的问题了。
由于袜子太多,swgr把它们随便地分装进了N个抽屉里,每个抽屉都装着一些袜子。这样一来,就会出现有的抽屉里的袜子是刚好能凑成若干双的,有的抽屉里的袜子却会多出一只。
另外,swgr还会不定期补充袜子的数量。有时他想知道:从第i个抽屉到第j个抽屉的所有抽屉里,有多少个抽屉里的袜子是刚好能凑成若干双呢?
Input
本题只有一组测试数据。输入数据的第一行为一个数N,表示有N个抽屉。
接下来一行有N个数,表示N个抽屉里初始时的袜子数。
接下来一行有一个数Q,表示一共有Q个操作。
接下来Q行,每行表示一个操作。操作有两类,一类操作是P a b,表示swgr买了b只袜子并放进了第a号抽屉中;另一类操作是C x y,表示swgr想知道现在从第x个抽屉到第y个抽屉的所有抽屉里(包括抽屉x和抽屉y),有多少个抽屉里的袜子刚好能凑成若干双。
数据范围:1≤N,Q≤100000,每个抽屉的初始袜子只数和每次买袜子的只数不超过20。抽屉编号为1号到N号。并保证1≤a≤N,1≤x≤y≤N。
Output
对于每个C操作,输出一行,表示对应问题的答案,即满足题意的抽屉的个数。
Sample Input
10
5 4 9 1 3 8 9 5 2 17
4
C 1 2
P 1 1
C 1 2
C 3 4
Sample Output
1
2
0
#include<stdio.h>
struct haha
{
int left;
int right;
int cnt;
int flag;
}node[100000*4];
int n;
void pushup(int nd)
{
// node[nd].flag=(node[nd*2].flag+node[nd*2+1].flag)%2;
node[nd].cnt=node[nd*2].cnt+node[nd*2+1].cnt;
}
void build(int left,int right,int nd)
{
int mid;
node[nd].left=left;
node[nd].right=right;
node[nd].cnt=0;
if(left==right)
{
scanf("%d",&node[nd].flag);
node[nd].flag=node[nd].flag%2;
if(node[nd].flag==0) {node[nd].cnt=1;}
else node[nd].cnt=0;
// printf("%d\n",node[nd].cnt);
return ;
}
mid=(left+right)/2;
build(left,mid,nd*2);
build(mid+1,right,nd*2+1);
pushup(nd);
}
int query(int left,int right,int nd)
{
if(node[nd].left==left&&node[nd].right==right)
{
return node[nd].cnt;
}
int mid=(node[nd].left+node[nd].right)/2;
if(left>mid) return query(left,right,nd*2+1);//////////大傻逼
else if(right<=mid) return query(left,right,nd*2);
else return query(left,mid,nd*2)+query(mid+1,right,nd*2+1);
// pushup(nd);
}
void update(int pos,int num,int nd)
{
if(node[nd].left==pos&&node[nd].right==pos)
{
node[nd].flag=(node[nd].flag+num)%2;
if(node[nd].flag==0) node[nd].cnt=1;
else node[nd].cnt=0;
// pushup(nd);
return ;
}
int mid=(node[nd].left+node[nd].right)/2;
if(pos>mid) update(pos,num,nd*2+1);
else update(pos,num,nd*2);
pushup(nd);
}
int main()
{
int a,b,m;
char s[2];
scanf("%d",&n);
build(1,n,1);
scanf("%d",&m);
while(m--)
{
scanf("%s%d%d",s,&a,&b);
if(s[0]=='P') update(a,b,1);
else if(s[0]=='C') printf("%d\n",query(a,b,1));
}
return 0;
}
分享到:
相关推荐
适用于XMU Health System的Auto_daily_report 介绍 支持在“承诺xxxx”的下拉框选择“是” :check_box_with_check: 支持保存表单 :check_box_with_check: 支持判断是否打卡成功 :check_box_with_check: 打卡失败,...
HA_ApexDC___V1.2.0_XMU.exe xmuer分享下载用,如需下载或转载,请联系原作者。 请勿用于商业用途!
XMU_related Something related with XMU 这个项目会放一些我在XMU所写的一些东西,基本都会和学校的东西有关 1. XMU各大网站信息的RSS订阅汇总 在文件夹下的Excel中,提供了一些常用的RSS订阅的链接。可以便捷地...
XMU OJ 1230的解题报告和源代码 菜鸟小李是xmu大x的学生了,可英语总数6x。四级考试临近了,临时抱佛脚的他买了本英语词汇,可是小李是个大穷人,随便街摊买了本盗版的新东方。回到宿舍才发现:书里的单词竟然是...
操作系统复习提纲
XMU操作系统课程实验.zip
2020-2021春季XMU信息检索大作业:自适应文本检索系统的实现 initialize.cpp 用于初始化服务器,即构造向量空间模型。这里包括: 获取全部文档的绝对路径,并将文档与一个数字编号一一映射; 读取全部文档,并将...
nachos:Nachos XMU操作系统课程实验
厦门大学oj部分习题的源代码,其中有关于深搜,广搜的,动态规划的。
厦门大学2017级研究生计算智能期末参考试卷,下载后可以和博主互相交流哦~
厦门大学(XMU) 单片机嵌入式开发课程 5个实验作业+源代码+文档说明 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的课程设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分...
根据2019年3月厦门大学研究生院公布的厦门大学研究生学位论文格式规范,和历届学长学姐传留下的资源,修改一份新版本《厦门大学研究生学位论文LaTeX模板》
1 给定下面的XML文档内容,根据要求为每个问题设计一个XSLT文件,并在浏览器中进行浏览以观察结果是否为所要求的形式。 2 写出此XML文档中按成绩由高到低排序的样式单文件。 3 编写book.xslt文档,要求在book.xml中...
XMU-LaTeX-Template XMU LaTeX Template 本模板经本人修改后(但正文非本人论文),可供作文厦大本科/双学位毕业论文模板的参考。 本人测试在MacTex下可以通过测试。 如果无法通过编译或者编译错误的话,有两点值得...
厦大常用网址,很多,有教务处,选课系统厦门大学青年志愿者服务管理系统 twi.xmu.edu.cn/vms/ 厦门大学网络教学平台(老版常用) http://course.xmu.edu.cn/meol/homepage/common/
【酒店管理系统】 酒店管理系统是一种用于帮助酒店管理和运营的软件系统。这种系统通常涵盖多个方面,包括客房预订、前台管理、客户关系管理、财务管理、员工管理、库存管理、报告和分析等。通过使用酒店管理系统,...
浙大硕士latex模板;参考于 https://github.com/TheNetAdmin/zjuthesis
libsvm-3.22_包含数据集(heart_scale.mat) 参考教程:http://blog.csdn.net/houchaoqun_xmu/article/details/69641641
用于在不使用Flash的情况下,上传文件到course.xmu.edu.cn的Chrome扩展。 这是什么? 最早在2021年之后,Chrome / Firefox / Edge都停止了对Flash的支持,而你厦这个老旧的课程平台上传了一个文件还得用Flash。这就...
Hadoop安装教程_伪分布式配置_CentOS6.4/Hadoop2.6.0_厦大数据库实验室博客总结、分享、收获大数据 (http://dblab.xmu.