【Codeforces Round 263 (Div 2)E】【坐标映射 脑洞】Appleman and a Sheet of Paper 折纸游戏 区间查询

本文主要是介绍【Codeforces Round 263 (Div 2)E】【坐标映射 脑洞】Appleman and a Sheet of Paper 折纸游戏 区间查询,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Appleman and a Sheet of Paper
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Appleman has a very big sheet of paper. This sheet has a form of rectangle with dimensions 1 × n. Your task is help Appleman with folding of such a sheet. Actually, you need to perform q queries. Each query will have one of the following types:

  1. Fold the sheet of paper at position pi. After this query the leftmost part of the paper with dimensions 1 × pi must be above the rightmost part of the paper with dimensions 1 × ([current width of sheet] - pi).
  2. Count what is the total width of the paper pieces, if we will make two described later cuts and consider only the pieces between the cuts. We will make one cut at distance li from the left border of the current sheet of paper and the other at distance ri from the left border of the current sheet of paper.

Please look at the explanation of the first test example for better understanding of the problem.

Input

The first line contains two integers: n and q (1  ≤ n ≤ 105; 1 ≤ q ≤ 105) — the width of the paper and the number of queries.

Each of the following q lines contains one of the described queries in the following format:

  • "1 pi(1 ≤ pi < [current width of sheet]) — the first type query.
  • "2 li ri(0 ≤ li < ri ≤ [current width of sheet]) — the second type query.
Output

For each query of the second type, output the answer.

Examples
input
7 4
1 3
1 2
2 0 1
2 1 2
output
4
3
input
10 9
2 2 9
1 1
2 0 1
1 8
2 0 8
1 2
2 1 3
1 4
2 2 4
output
7
2
10
4
5
Note

The pictures below show the shapes of the paper during the queries of the first example:

After the first fold operation the sheet has width equal to 4, after the second one the width of the sheet equals to 2.



#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 1e5+10, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int n, q;
int o, p, l, r;
int a[N];
int s[N];
int L, R; bool flip;
void init()
{L = 1; R = n;for (int i = 1; i <= n; ++i){a[i] = 1;s[i] = s[i - 1] + a[i];}flip = 0;
}
void solve()
{while (q--){scanf("%d", &o);if (o == 1){int len = R - L + 1;scanf("%d", &p);if (!flip){//翻转部分更少,我们进行翻转if (p <= len - p){int l = L + p;int r = L + p + p - 1;int U = l + l - 1;s[l - 1] = 0;for (int i = l; i <= r; ++i){a[i] += a[U - i];s[i] = s[i - 1] + a[i];}L += p;}//不翻转部分更少,我们反向操作else{p = len - p;int l = R - p - p + 1;int r = R - p;int U = r + r + 1;for (int i = l; i <= r; ++i){a[i] += a[U - i];s[i] = s[i - 1] + a[i];}R -= p;flip = 1;}}else{//翻转部分更少,我们进行翻转if (p <= len - p){int l = R - p - p + 1;int r = R - p;int U = r + r + 1;for (int i = l; i <= r; ++i){a[i] += a[U - i];s[i] = s[i - 1] + a[i];}R -= p;}//不翻转部分更少,我们反向操作else{p = len - p;int l = L + p;int r = L + p + p - 1;int U = l + l - 1;s[l - 1] = 0;for (int i = l; i <= r; ++i){a[i] += a[U - i];s[i] = s[i - 1] + a[i];}L += p;flip = 0;}}}else{scanf("%d%d", &l, &r); --r;int ans;if (!flip)ans = s[L + r] - s[L + l - 1];else ans = s[R - l] - s[R - r - 1];printf("%d\n", ans);}}
}
int main()
{while (~scanf("%d%d", &n, &q)){init();solve();}return 0;
}
/*
【trick&&吐槽】
CFdiv2E并不一定很难。毕竟诗诗都想出来怎么做了233>_<【题意】
给你一张1*n(1e5)的纸条,纸条上有0~n共计n个刻度。
我们有q(1e5)个操作。
对于每个操作,有两种类型:
(1,pi),表示我们把纸条的[0,pi]向右翻转。
(2,l,r),表示我们查询l~r区间段有多少个纸条单位【类型】
复杂度分析 坐标映射【分析】
其实,我们每次只要翻转较小的一侧就好了。
唯一需要处理的是坐标映射。
我们只要记录一个实际区间,同时记录flip表示是否翻转过。
如果未翻转过,操作从从左往右翻转,从左往右查询。
如果翻转过,操作从右向左翻转,从右向左查询【时间复杂度&&优化】
总翻转长度不会超过n,复杂度为O(n)【数据】
10 100
1 9
2 0 1
2 0 2
2 0 3
2 0 9*/


这篇关于【Codeforces Round 263 (Div 2)E】【坐标映射 脑洞】Appleman and a Sheet of Paper 折纸游戏 区间查询的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/744487

相关文章

使用Python从PPT文档中提取图片和图片信息(如坐标、宽度和高度等)

《使用Python从PPT文档中提取图片和图片信息(如坐标、宽度和高度等)》PPT是一种高效的信息展示工具,广泛应用于教育、商务和设计等多个领域,PPT文档中常常包含丰富的图片内容,这些图片不仅提升了... 目录一、引言二、环境与工具三、python 提取PPT背景图片3.1 提取幻灯片背景图片3.2 提取

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

SQL表间关联查询实例详解

《SQL表间关联查询实例详解》本文主要讲解SQL语句中常用的表间关联查询方式,包括:左连接(leftjoin)、右连接(rightjoin)、全连接(fulljoin)、内连接(innerjoin)、... 目录简介样例准备左外连接右外连接全外连接内连接交叉连接自然连接简介本文主要讲解SQL语句中常用的表

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

MySQL中的交叉连接、自然连接和内连接查询详解

《MySQL中的交叉连接、自然连接和内连接查询详解》:本文主要介绍MySQL中的交叉连接、自然连接和内连接查询,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、引入二、交php叉连接(cross join)三、自然连接(naturalandroid join)四

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

resultMap如何处理复杂映射问题

《resultMap如何处理复杂映射问题》:本文主要介绍resultMap如何处理复杂映射问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录resultMap复杂映射问题Ⅰ 多对一查询:学生——老师Ⅱ 一对多查询:老师——学生总结resultMap复杂映射问题

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co