JZOJ3798 臨洮巨人

2022-09-23 07:46:59 字數 929 閱讀 1648

半簽到題我居然沒有做出來\(qwq\)。

設\(cnt[x][1/2/3]\)表示前\(i\)個子母中,字母\(a,b,c\)分別出現的次數。

那麼一段區間\([l,r]\)的\(a,b,c\)數量相同,當且僅當\(cnt[r][1]-cnt[l-1][1]=cnt[r][2]-cnt[l-1][2]=cnt[r][3]-cnt[l-1][3]\)。

也就是需要分別滿足

令\(p[i]=cnt[i][1]-cnt[i][2],q[i]=cnt[i][1]-cnt[i][3]\),那麼如果有兩個位置\(x,y\),滿足\(p[x]=p[y]\)且\(q[x]=q[y]\)且\(x>y\),那麼\([y+1,x]\)就是一個滿足條件的區間。

我們考慮把二維壓為一維,也就是令\(t[x]=10^6\times p[x]+q[x]\),那麼如果\(t[x]=t[y]\)且\(y,那麼\([y+1,x]\)就是一個滿足條件的區間。

所以就把每個位置的\(t\)求出來,排序然後指標掃描即可。

#include #include #include using namespace std;

typedef long long ll;

const int n=1000010;

int n,m,num,a[n];

ll ans,cnt[n][4],t[n];

char ch[n];

int main()

n++;

sort(t+1,t+1+n);

for (int i=1,j=1;i<=n;i=j=j+1)

printf("%lld",ans/2ll);

return 0;

}