大致题意： 给定一个由"J"、"O"、"I"三个字母组成的字符串，求最长一段连续子串的长度，满足这段串中"J"、"O"、"I"三个字母数量相等。
前言
没错，我只是来水一发博客的。。。
很好奇为什么能在哈希和平衡树的分类里找到这道题。。。
顺便提一下，(AtCoder)上输出没换行结果挂了一发。。。
大致想法
这道题真的挺水的。
我们设(s_{i,0/1/2})分别表示前(i)个字符中"J"、"O"、"I"的数量（即前缀和）。
显然，若([j+1,i])这个区间是合法的，就有：
[s_{i,0}-s_{j,0}=s_{i,1}-s_{j,1}=s_{i,2}-s_{j,2}
]
千万不要被这么多项蒙蔽你的双眼，实际上这个式子可以拆成：
[s_{i,0}-s_{j,0}=s_{i,1}-s_{j,1}
]
[s_{i,1}-s_{j,1}=s_{i,2}-s_{j,2}
]
然后我们把含(i)的项扔一边，含(j)的扔另一边，就会发现：
[s_{i,0}-s_{i,1}=s_{j,0}-s_{j,1}
]
[s_{i,1}-s_{i,2}=s_{j,1}-s_{j,2}
]
于是，我们只要把(s_{i,0}-s_{i,1},s_{i,1}-s_{i,2})绑起来排个序，然后找出最大的(i-j)即可。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
#define Gmax(x,y) (x<(y)&&(x=(y)))
#define swap(x,y) (x^=y^=x^=y)
using namespace std;
int n,s[N+5][3];char st[N+5];
struct data
{
int id,x,y;I data(CI p=0,CI a=0,CI b=0):id(p),x(a),y(b){}
I bool operator < (Con data& o) Con {return x^o.x?x<o.x:(y^o.y?y<o.y:id<o.id);}//排序
}p[N+5];
int main()
{
RI i;for(scanf("%d%s",&n,st+1),i=1;i<=n;++i) s[i][0]=s[i-1][0],
s[i][1]=s[i-1][1],s[i][2]=s[i-1][2],++s[i][st[i]=='J'?0:(st[i]=='O'?1:2)],//前缀和
p[i]=data(i,s[i][0]-s[i][1],s[i][1]-s[i][2]);//绑起来
RI ans=0;for(sort(p,p+n+1),i=1;i<=n;++i) p[i].x==p[i-1].x&&
p[i].y==p[i-1].y&&(Gmax(ans,p[i].id-p[i-1].id),swap(p[i].id,p[i-1].id));//注意对于多个相同的，要用最大的i减去最小的j
return printf("%d
",ans),0;
}