【莫队】bzoj4866: [Ynoi2017]由乃的商场之旅
2024-08-27 15:36:59
莫队的一些套路
Description
由乃有一天去参加一个商场举办的游戏。商场派了一些球王排成一行。每个人面前有几堆球。说来也巧,由乃和你
一样,觉得这游戏很无聊,于是决定换一个商场。另一个商场是Deus的,他看到由乃来了,于是想出了一个更有趣
的游戏:写数据结构题这个题是这样的:
我们的情人,不过是随便借个名字,用幻想吹出来的肥皂泡,把信拿去吧,你可以使假戏成真。我本来是无病呻吟
,漫无目的的吐露爱情---现在这些漂泊不定的鸟儿有地方栖息了,你可以从信里看出来。拿去吧---由于不是出自
真心,话就说得格外动听,拿去吧,就这么办吧...由于世界会在7月20日完结,作为救世主,间宫卓司要在19日让
所有人回归天空现在已经是19日傍晚,大家集合在C栋的天台上,一共n个人在他们面前,便是终之空,那终结的天
空
回归天空是一件庄重的事情,所以卓司决定让大家分批次进行,给每个人给了一个小写字母'a'->'z'作为编号一个
区间的人如果满足他们的编号重排之后可以成为一个回文串,则他们可以一起回归天空,即这个区间可以回归天空
由于卓司是一个喜欢妄想的人,他妄想了m个区间,每次他想知道每个区间中有多少个子区间可以回归天空因为世
界末日要来了,所以卓司的信徒很多
由乃天天做数据结构已经快恶心死了,于是让您帮她做当然,您天天做数据结构题,肯定也觉得恶心死了,不过可
爱即正义!所以这个题还是要做的~
Input
第一行两个数n,m
之后一行一个长为n的字符串,代表每个人的编号
之后m行每行两个数l,r代表每次卓司妄想的区间
n,m<=60000
Output
m行,每行一个数表示答案
Sample Input
6 6
zzqzzq
1 6
2 4
3 4
2 3
4 5
1 1
zzqzzq
1 6
2 4
3 4
2 3
4 5
1 1
Sample Output
16
4
2
2
3
1
4
2
2
3
1
题目分析
应该是一类常见套路:考虑每加入一个元素对于已知区间的贡献。
那么这里把每个字母看成$2^i$,先预处理出每一个位置的异或前缀和,莫队查询时答案增上全为偶次的字符+枚举为奇数的字母的贡献即可。
注意莫队中加入与删除操作的顺序,这个有些时候是会相互影响的。
然后用unsigned short int卡空间,就好了。
#include<bits/stdc++.h>
#define S(p) cnt[tmp^(1<<p)]
#define Add(val) tmp=c[val],nw+=cnt[tmp],nw+=S(0)+S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11)+S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20)+S(21)+S(22)+S(23)+S(24)+S(25),++cnt[tmp]
#define Del(val) tmp=c[val],--cnt[tmp],nw-=cnt[tmp],nw-=S(0)+S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11)+S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20)+S(21)+S(22)+S(23)+S(24)+S(25)
const int maxn = ;
const int maxp = ; int blk[maxn],size;
struct QRs
{
int l,r,id;
bool operator < (QRs a) const
{
return blk[l]==blk[a.l]?(blk[l]&?r < a.r:r > a.r):blk[l] < blk[a.l];
}
}q[maxn];
int n,m,c[maxn],ans[maxn],L,R,nw,tmp;
unsigned short cnt[maxp];
char s[maxn]; int read()
{
char ch = getchar();
int num = , fl = ;
for (; !isdigit(ch); ch=getchar())
if (ch=='-') fl = -;
for (; isdigit(ch); ch=getchar())
num = (num<<)+(num<<)+ch-;
return num*fl;
}
int main()
{
n = read(), m = read(), scanf("%s",s+);
size = std::min(*(int)sqrt(n+0.5), n)+;
for (int i=; i<=n; i++) blk[i] = i/size, c[i] = c[i-]^(<<(s[i]-'a'));
for (int i=; i<=m; i++) q[i].l = read()-, q[i].r = read(), q[i].id = i;
std::sort(q+, q+m+);
L = , R = ;
for (int i=; i<=m; i++)
{
while (L > q[i].l) --L, Add(L);
while (R < q[i].r) ++R, Add(R);
while (L < q[i].l) Del(L), ++L;
while (R > q[i].r) Del(R), --R;
ans[q[i].id] = nw;
}
for (int i=; i<=m; i++) printf("%d\n",ans[i]);
return ;
}
END
最新文章
- 计算机网络学习笔记--数据链据层之MAC子层(整理)
- jQuery中json对象与json字符串互换
- rsync+inotify实现自动备份
- luogu p1268 树的重量——构造,真正考验编程能力
- MySql获取表的字段名称、字段注解、字段类型、字段长度
- CSS之Document方法的使用
- android源码编译环境的准备及编译之后使用emulator运行的方法 - 官方版
- android蓝牙4.0(BLE)开发之ibeacon初步
- 解决TextView与RadioGroup不对齐的问题
- ViewSwitcher的功能与用法
- UUID.randomUUID().toString() 的作用
- 一脸懵逼学习基于CentOs的Hadoop集群安装与配置
- ORACLE的锁机制
- Java-String.intern的深入研究
- 第四十八条:如果需要精确的答案,请避免使用float和double
- oo第一次总结博客
- 按奇偶排序数组 II
- HTTP进阶学习笔记
- 你的APK安全吗?来WeTest免费测!
- 改maven下创建的动态网站依赖的jre版本