洛谷3604 美好的每一天

鬼畜卡常

Posted by yjjr's blog on March 7, 2018

标签:莫队

题目

题目传送门

题目背景

时间限制3s,空间限制162MB

素晴らしき日々

我们的情人,不过是随便借个名字,用幻想吹出来的肥皂泡,把信拿去吧,你可以使假戏成真。我本来是无病呻吟,漫无目的的吐露爱情—现在这些漂泊不定的鸟儿有地方栖息了,你可以从信里看出来。拿去吧—由于不是出自真心,话就说得格外动听,拿去吧,就这么办吧…

由于世界会在7月20日完结,作为救世主,间宫卓司要在19日让所有人回归天空

现在已经是19日傍晚,大家集合在C栋的天台上,一共n个人

在他们面前,便是终之空,那终结的天空

题目描述

回归天空是一件庄重的事情,所以卓司决定让大家分批次进行,给每个人给了一个小写字母’a’->’z’作为编号

一个区间的人如果满足他们的编号重排之后可以成为一个回文串,则他们可以一起回归天空,即这个区间可以回归天空

由于卓司是一个喜欢妄想的人,他妄想了m个区间,每次他想知道每个区间中有多少个子区间可以回归天空

因为世界末日要来了,所以卓司的信徒很多

输入格式

第一行两个数n,m

之后一行一个长为n的字符串,代表每个人的编号

之后m行每行两个数l,r代表每次卓司妄想的区间

输出格式

m行,每行一个数表示答案

样例

输入样例#1

6 6
zzqzzq
1 6
2 4
3 4
2 3
4 5
1 1

输出样例#1

16
4
2
2
3
1

提示与说明

对于10%的数据,n,m<=100

对于30%的数据,n,m<=2000

对于100%的数据,n,m<=60000

字符集大小有梯度

在大家回归天空之后,彩名露出了阴冷的笑容

分析

这题太毒瘤了!疯狂卡常

我是不会告诉你们我开了O2才AC的


一个区间可以重排成为回文串,即区间中最多有一个字母出现奇数次,其他的都出现偶数次

这个原理和XOR类似

如果一个区间的异或和为0或2^x,则可以重排成为回文串

用a数组记录1->i的异或和

然后莫队解决

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=6e4+6;
int n,m,t,blo,belong[maxn],a[maxn],ans[maxn],re;
unsigned short cnt[1<<26]; 
char s[maxn];

struct ask{int l,r,pos;}q[maxn];
inline bool cmp(ask a,ask b){
	return belong[a.l]^belong[b.l]?belong[a.l]<belong[b.l]:belong[a.l]&1?a.r<b.r:a.r>b.r;
} 
void insert(int x){
	rep(i,0,t-1)re+=cnt[x^(1<<i)];
	re+=cnt[x]++;
}
void erase(int x){
	rep(i,0,t-1)re-=cnt[x^(1<<i)];
	re-=--cnt[x];
}
int main()
{
	n=read(),m=read();scanf("%s",s+1);
	rep(i,1,n)t=max(t,s[i]-'a'+1);
	blo=n/sqrt(m*2/3);
	rep(i,1,n)belong[i]=(i-1)/blo,a[i]=a[i-1]^(1ll<<s[i]-'a');
	rep(i,1,m)q[i].l=read(),q[i].r=read(),q[i].pos=i;
	sort(q+1,q+1+m,cmp);
	for(int i=1,l=1,r=0;i<=m;i++){
		while(l>q[i].l)insert(a[--l]);
		while(r<q[i].r)insert(a[++r]);
		while(l<q[i].l)erase(a[l++]);
		while(r>q[i].r)erase(a[r--]);
		insert(a[l-1]);
		ans[q[i].pos]=re;
		erase(a[l-1]);
	}
	rep(i,1,m)cout<<ans[i]<<endl;
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr