logo AlgoBeat OnlineJudge
登录 注册

#10075. [Sleeping Cup #5] F. Inversion

内存限制：512 MiB 时间限制：2000 ms 输入文件：inversion.in 输出文件：inversion.out
题目类型：传统 评测方式：文本比较
上传者： 匿名
提交 提交记录 统计 测试数据 讨论 题解

题目描述

https://atcoder.jp/contests/practice2/tasks/practice2_l

注记：

由于评测机性能差异，本题的时间限制由 1 秒改为 2 秒。

由于本题不涉及负数，你可以全程使用 unsigned int 计算以优化代码常数。

本题中 01 串的下标从 开始计数。

本题的 IO 量很大，因此请注意 IO 效率。

你可以使用以下代码（使用时需要包含 <cstdio> 或 <bits/stdc++.h> 头文件），并用 read() 读入一个非负整数，用 writeline(x) 输出一行一个非负整数 ：

inline unsigned read()
{
	unsigned x = 0;
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0') x = x * 10 + c - '0', c = getchar_unlocked();
	return x;
}
inline void write(unsigned x)
{
	if (!x) return;
	write(x / 10);
	putchar_unlocked(x % 10 + '0');
}
inline void writeline(unsigned x)
{
	if (x) write(x);
	else putchar_unlocked('0');
	putchar_unlocked('\n');
}

以下是本题的一些定义：

  • 「区间 的内部逆序对」被定义为满足以下三个条件的正整数对 ：
    • 。
    • 。
    • 。
  • 「反转区间 」被定义为以下操作：
    • 对于区间 中的每一位 ：
      • 如果 ，那么执行操作 ，即把它变成 。
      • 如果 ，那么执行操作 ，即把它变成 。

现有一个长度为 且初始全为 的 01 串 。

你需要执行以下两种指令各 个，共计 个：

  • 对于第 个指令，给定两个整数 ，反转区间 。
  • 对于第 个指令，给定两个整数 ，求出区间 的内部逆序对个数。

输入格式

第一行两个正整数 。

下面 行，每行两个非负整数 。

输出格式

行，每行一个非负整数，分别表示第 个指令的答案。

数据范围与提示

下发文件

请在测试数据中下载下发文件 down.cpp。

我们下发了 down.cpp 作为 Generator，但没有下发样例。

请在编译 down.cpp 为可执行文件 down 后使用以下命令生成样例：

  • down inversion.in inversion.ans（Windows）
  • ./down inversion.in inversion.ans（Linux）

数据范围

  • 对于上述 Generator 生成的样例数据，。
  • 对于实际测试数据，，。
  • 保证实际测试数据的生成策略与上述 Generator 相同。
  • 不保证实际测试数据与上述 Generator 使用了相同的随机数生成器。
  • 保证 。

显示分类标签

编辑器加载中 …
Powered by SYZOJ. Modified by Zemu (UnratedCheater).
项目源码 · 新ICP备2026003452号-2
当前版本：V1.7.1