真·美好的每一天（美好個鬼啊）

真·調了一下午

原因是，我之前移動指針時沒有先擴再縮，所以導致區間是負的；但是正常來說也沒事，可是這題卡常，桶我開的是 unsigned short ，于是區間是負的，自然桶中會有負數，負數爆成正的爽（霧）。

顯然一段區間是回文的當且僅當至多有一個字母出現奇數次，于是我們嘗試用異或去解這道題。

我們還是類似前綴異或的思路來取出區間異或值，并枚舉多出來的字母是哪個即可（這樣會T）。

于是我們可以在最開始預處理出有用的狀態，就是滿足 \(a[i] \bigoplus (1<<i)\) 是存在的狀態存起來即可。（其實跑滿好像是一樣的）

比較暴力的寫法。

inline void add(int x) {

	anss+=c[a[x]]++;

	for(R i=0;i<L;++i)

		anss+=c[a[x]^(1<<i)];

}

inline void sub(int x) {

	anss-=--c[a[x]];

	for(R i=0;i<L;++i)

		anss-=c[a[x]^(1<<i)];

}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<bitset>

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0,f=1;

	register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;

	do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;

} const int N=60001,M=(1<<26)+1,L=26;

#define u16 unsigned short

struct node { int l,r,id,pos;

	inline bool operator < (const node& that) const

		{return pos==that.pos?pos&1?r<that.r:r>that.r:l<that.l;}

}q[N];

int n,m,B,a[N];

int anss,ans[N],d[N][L];

bitset<M> tg;

char s[N],cnt[N]; u16 c[M];

inline void add(int x) {

	anss+=c[a[x]]++;

	for(R i=0;i<cnt[x];++i)

		anss+=c[d[x][i]];

}

inline void sub(int x) {

	anss-=--c[a[x]];

	for(R i=0;i<cnt[x];++i)

		anss-=c[d[x][i]];

}

inline void main() {

	n=g(),m=g(),scanf("%s",s+1);

	B=sqrt(n+1); tg[0]=1;

	for(R i=1;i<=n;++i) tg[(a[i]=a[i-1]^(1<<(s[i]-'a')))]=1;

	for(R i=0;i<=n;++i) for(R j=0,t=1;j<L;++j,t<<=1)

		if(tg[a[i]^t]) d[i][cnt[i]++]=a[i]^t;

	for(R i=1;i<=m;++i)

		q[i].l=g()-1,q[i].r=g(),q[i].id=i,

		q[i].pos=q[i].l/B;

	sort(q+1,q+m+1);

	for(R i=1,l=1,r=0;i<=m;++i) {

		while(l>q[i].l) add(--l); while(r<q[i].r) add(++r);

		while(l<q[i].l) sub(l++); while(r>q[i].r) sub(r--);

		ans[q[i].id]=anss;

	}

	for(R i=1;i<=m;++i) printf("%d\n",ans[i]);

}

} signed main() {Luitaryi::main(); return 0;}

2019.11.25

總結

以上是生活随笔為你收集整理的P3604 美好的每一天的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。