P3604 美好的每一天
題目背景
時間限制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
3
1
輸入 #2
aaabbb
1 2
5 6
輸出 #2
17
輸入 #3
4 1
yuno
1 4
輸出 #3
說明/提示
對于10%的資料，\(n,m<=100\)
對于30%的資料，\(n,m<=2000\)
對于100%的資料，\(n,m<=60000\)
字元集大小有梯度
在大家回歸天空之後，彩名露出了陰冷的笑容
Solution
簡化一下題意,給你一個區間,讓你求它的子區間内的序列是回文串的個數
ps:這裡說的回文串是指序列任意重排後是回文串
既然是 重排 ,也就是說一段序列是回文串當且僅當這段序列所有字元出現的次數要麼全是偶數,要麼隻有一個奇數
也就是這兩種
abccba
abcba
那麼我們用一個26位二進制數來表示目前區間内各字母出現次數的奇偶性,0表示偶數,1表示奇數
字首和優化,通過異或操作來求出一個區間内各字母的奇偶性
char s; cin>>s;
s[i]=1<<(s-'a');
s[i]^=s[i-1];
這是求異或字首和
到了這裡,做這道題之前建議先看看這題P4462 [CQOI2018]異或序列
這是題解
接下來的大部分操作都和 異或序列 這道題一樣
異或的性質
已知a^b=c
則a^c=b,b^c=a
求一段序列\([l,r]\)的異或和就是\(s_{l-1}\bigoplus s_r\),其中\(s[]\)是我們剛才求的異或字首和數組
下面就是莫隊了
上面說過滿足條件的區間一定是各字母出現次數全為偶數,轉化成數字就是\(0\),或者是某一個字母出現次數為基數,轉化成數字就是這個26位二進制數中有且僅有一位為\(1\)
即區間的異或和要麼為0,要麼為2^x
結合之前異或的性質
\(a_x \bigoplus a_{x+1} \bigoplus ... \bigoplus a_y = k\)\(\Rightarrow\)\(s_{x-1}\bigoplus s_r=k\)\(\Rightarrow\)\(s_{r}\bigoplus k=s_{x-1}\)
這個\(k\)就是\(0\)和\(2^x\),共27個狀态
當我們加入一個值\(a[x]\)時,我們想要知道目前所在區間有多少個\(a[i]\bigoplus a[x]=k\),其中\(i<x\),也就是\(a[x]\bigoplus k\)的個數,因為這些數都可以和\(a[x]\)異或起來得到\(k\)
il void add(int x) {
ans+=cnt[a[x]];
for (rg int i=0;i<26;i++)
ans+=cnt[a[x]^(1<<i)];
cnt[a[x]]++;
}
删除同理
il void remove(int x) {
cnt[a[x]]--;
ans-=cnt[a[x]];
for (rg int i=0;i<26;i++)
ans-=cnt[a[x]^(1<<i)];
}
至于為什麼\(add()\)函數是先更新\(ans\),在\(cnt[]++\),而\(remove()\)函數是先\(cnt[]--\)再更新\(ans\),在于\(k=0\)的情況
當\(k=0\)時,\(a[x]\bigoplus k=a[x]\),如果我們先用\(ans\)減去貢獻,再使\(cnt[]--\),答案會少一
原因就是我們要統計的其實是\(i<x\)的\(cnt[a[x]]\)的個數,不能把第\(x\)個位置上的值算進去,是以需要先\(cnt[a[x]]--\),再用\(ans\)減去貢獻
還有一點這道題卡空間還卡時間
我們的\(cnt[(1<<26)+5]\)數組,開\(int\)是開不下的,我開的是\(short\),另外塊的大小也不能開\(\sqrt n\),要開\(3\times \sqrt n\)
(你問我為啥,我也不知道,莫隊塊的大小我一直搞不清)
Code
#include<bits/stdc++.h>
#define il inline
#define rg register
#define lol long long
#define in(i) (i=read())
using namespace std;
const int N=6e4+5;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+(i^48),i=getchar();
return ans*f;
}
int n,m,k,block,ans;
int a[N],sum[N];
short cnt[(1<<26)+5];
struct query{
int l,r,id,pos;
bool operator < (const query &a) const {
return pos==a.pos?r<a.r:pos<a.pos;
}
}t[N];
il void add(int x) {
ans+=cnt[a[x]];
for (rg int i=0;i<26;i++)
ans+=cnt[a[x]^(1<<i)];
cnt[a[x]]++;
}
il void remove(int x) {
cnt[a[x]]--;
ans-=cnt[a[x]];
for (rg int i=0;i<26;i++)
ans-=cnt[a[x]^(1<<i)];
}
int main() {
in(n), in(m); block=3*sqrt(n);
for (rg int i=1;i<=n;i++) {
rg char s; cin>>s;
a[i]=1<<(s-'a');
a[i]^=a[i-1];
}
for (rg int i=1,l,r;i<=m;i++) {
in(l), in(r);
t[i].l=l-1, t[i].r=r;
t[i].id=i;
t[i].pos=(l-1)/block+1;
}
sort(t+1,t+1+m);
for (rg int i=1,curl=1,curr=0;i<=m;i++) {
rg int l=t[i].l,r=t[i].r;
while(curl<l) remove(curl++);
while(curl>l) add(--curl);
while(curr<r) add(++curr);
while(curr>r) remove(curr--);
sum[t[i].id]=ans;
}
for (rg int i=1;i<=m;i++) cout<<sum[i]<<endl;
}
部落客蒟蒻