Problem: rainbow_string (2016 finals)

// RAINBOW STRING // Official Solution by Jacob Plachta #define DEBUG 0
#include  #include  #include  #include  #include  #include  #include  #include
#include  #include  #include  #include  #include  #include  #include  #include
#include  #include  #include  #include  #include  #include  using namespace
std; #define LL long long #define LD long double #define PR pair #define
Fox(i,n) for (i=0; i=0; i--) #define FoxR1(i,n) for (i=n; i>0; i--) #define
FoxRI(i,a,b) for (i=b; i>=a; i--) #define Foxen(i,s) for (i=s.begin();
i!=s.end(); i++) #define Min(a,b) a=min(a,b) #define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size()) #define All(s) (s).begin(),(s).end() #define
Fill(s,v) memset(s,v,sizeof(s)) #define pb push_back #define mp make_pair
#define x first #define y second template T Abs(T x) { return(x<0 ? -x : x); }
template T Sqr(T x) { return(x*x); } string plural(string s) { return(Sz(s) &&
s[Sz(s)-1]=='x' ? s+"en" : s+"s"); } const int INF = (int)1e9; const LD EPS =
1e-9; const LD PI = acos(-1.0); //#if DEBUG #define GETCHAR getchar /*#else
#define GETCHAR getchar_unlocked #endif*/ bool Read(int &x) { char c,r=0,n=0;
x=0; for(;;) { c=GETCHAR(); if ((c<0) && (!r)) return(0); if ((c=='-') &&
(!r)) n=1; else if ((c>='0') && (c<='9')) x=x*10+c-'0',r=1; else if (r) break;
} if (n) x=-x; return(1); } #define LIM 400005 int N,SZ; char S[LIM],C[LIM];
int sum[LIM][26]; int sz,P[20][LIM]; pair V[LIM]; int O[LIM],ind[LIM]; vector
Q[LIM],A[LIM],B[LIM]; int BLT[(1<<18)+1]; void BuildSuffixArray() { int i,s;
if (N==1) { sz=1; P[0][0]=0; return; } Fox(i,N) P[0][i]=S[i]; for (sz=s=1;
s=BLT[t]) { i=t; k-=BLT[t]; } b>>=1; } return(i); } int main() { if (DEBUG)
freopen("in.txt","r",stdin); int T,t; int M; int i,j,k,c,s; LL ans[26];
Read(T); Fox1(t,T) { Read(N),Read(M); scanf("%s%s",&S,&C); Fox(i,M) {
Read(j),Read(k); Q[j].pb(k); } Fill(sum,0); Fox1(i,N) Fox(j,26)
sum[i][j]=sum[i-1][j]+bool(S[i-1]=='A'+j); BuildSuffixArray(); Fox(i,N) {
O[i]=P[sz-1][i]; ind[O[i]]=i; } j=k=1; FoxR(i,N) { j++,k++; if (C[i]=='G')
j=1; if (C[i]=='R') k=1; if (j<k) { A[j].pb(O[i]); B[k].pb(O[i]); } }
Fill(BLT,0),s=0; for (SZ=1; SZ<N; SZ<<=1); Fill(ans,0); Fox1(i,N) {
Fox(j,Sz(A[i])) Update(A[i][j]+1,1),s++; Fox(j,Sz(B[i]))
Update(B[i][j]+1,-1),s--; Fox(j,Sz(Q[i])) { k=ind[Query(Q[i][j]-1)]; Fox(c,26)
ans[c]+=sum[k+i][c]-sum[k][c]; } } printf("Case #%d:",t); Fox(i,26) printf("
%lld",ans[i]); printf("\n"); Fox1(i,N+1) { A[i].clear(); B[i].clear();
Q[i].clear(); } } return(0); }



Sample input:
5
6 3
ABABAB
GGBGRG
2 1
2 2
2 3
3 3
XYZ
GGG
1 1
2 1
3 1
5 4
AAAAB
GBBBG
1 1
1 2
2 1
2 2
9 8
EDCBABCDE
GGGGRGGGG
1 6
1 7
1 8
2 1
2 2
2 3
4 1
4 2
21 8
FOXENISTHEPLURALOFFOX
BBGBGGBRGBGBBBBGRBGGB
1 8
2 7
3 6
4 5
5 4
6 3
7 2
8 1


Sample output:
Case #1: 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Case #2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2 1
Case #3: 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Case #4: 0 4 5 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Case #5: 2 0 0 0 5 1 0 4 2 0 0 6 0 1 1 4 0 3 2 0 3 0 0 2 0 0



Code: // RAINBOW STRING
// Official Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

//#if DEBUG
#define GETCHAR getchar
/*#else
#define GETCHAR getchar_unlocked
#endif*/

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 400005

int N,SZ;
char S[LIM],C[LIM];
int sum[LIM][26];
int sz,P[20][LIM];
pair<PR,int> V[LIM];
int O[LIM],ind[LIM];
vector<int> Q[LIM],A[LIM],B[LIM];
int BLT[(1<<18)+1];

void BuildSuffixArray()
{
	int i,s;
		if (N==1)
		{
			sz=1;
			P[0][0]=0;
			return;
		}
		Fox(i,N)
			P[0][i]=S[i];
		for (sz=s=1; s<N; sz++,s<<=1)
		{
				Fox(i,N)
					V[i]=mp(mp(P[sz-1][i],(i+s<N ? P[sz-1][i+s] : -1)),i);
			sort(V,V+N);
				Fox(i,N)
					if ((i) && (V[i].x==V[i-1].x))
						P[sz][V[i].y]=P[sz][V[i-1].y];
					else
						P[sz][V[i].y]=i;
		}
}

void Update(int i, int v)
{
	while (i<=SZ)
	{
		BLT[i]+=v;
		i+=(i&-i);
	}
}

int Query(int k)
{
	int i=0,b=SZ,t;
		while ((b) && (i<SZ))
		{
			t=i+b;
				if (k>=BLT[t])
				{
					i=t;
					k-=BLT[t];
				}
			b>>=1;
		}
	return(i);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	int T,t;
	int M;
	int i,j,k,c,s;
	LL ans[26];
	Read(T);
		Fox1(t,T)
		{
			Read(N),Read(M);
			scanf("%s%s",&S,&C);
				Fox(i,M)
				{
					Read(j),Read(k);
					Q[j].pb(k);
				}
			Fill(sum,0);
				Fox1(i,N)
					Fox(j,26)
						sum[i][j]=sum[i-1][j]+bool(S[i-1]=='A'+j);
			BuildSuffixArray();
				Fox(i,N)
				{
					O[i]=P[sz-1][i];
					ind[O[i]]=i;
				}
			j=k=1;
				FoxR(i,N)
				{
					j++,k++;
						if (C[i]=='G')
							j=1;
						if (C[i]=='R')
							k=1;
						if (j<k)
						{
							A[j].pb(O[i]);
							B[k].pb(O[i]);
						}
				}
			Fill(BLT,0),s=0;
				for (SZ=1; SZ<N; SZ<<=1);
			Fill(ans,0);
				Fox1(i,N)
				{
					Fox(j,Sz(A[i]))
						Update(A[i][j]+1,1),s++;
					Fox(j,Sz(B[i]))
						Update(B[i][j]+1,-1),s--;
					Fox(j,Sz(Q[i]))
					{
						k=ind[Query(Q[i][j]-1)];
							Fox(c,26)
								ans[c]+=sum[k+i][c]-sum[k][c];
					}
				}
			printf("Case #%d:",t);
				Fox(i,26)
					printf(" %lld",ans[i]);
			printf("\n");
				Fox1(i,N+1)
				{
					A[i].clear();
					B[i].clear();
					Q[i].clear();
				}
		}
	return(0);
}