問題概要
N匹の魚がいる.
これらは赤, 青, 緑のいずれかの色になっている.
魚は体長が自分の2倍以上ある魚に食べられてしまうので一緒にできない.
一緒にできる魚の色の組合せを求めよ
（中文概述）
N条鱼，鱼有身长和三种不同的颜色，
给定身长和颜色，挑一些鱼，三种颜色的鱼的数量构成三元组，
身长差距超过两倍的鱼不能在一个组内，
求可能的三元组个数。
解法
etにalgorithmのlower_boundを使っていてTLE死した.
ある魚に対してそれより小さい魚のうち一緒にいられる魚を考える.
この時赤がr匹, 青がb匹, 緑がg匹いるとするとその選び方は3辺の長さがr, b, gの直方体の内部の格子点の数に一致する(=3辺がr+1,b+1,g+1の直方体の体積).
これは赤, 青, 緑の選ぶ数に対して頂点が選べることからわかる.
この組は魚の体長をソートしておけばしゃくとり法する感じで求められる.
よってそのようなものを全て列挙して, 直方体を重ねあわせた体積を求める問題になる.
上から下に積分していけば, 各イベント点(各直方体のてっぺん)で長方形の和をとっていくことで断面が求められる.
各直方体は軸に接するように置いていると考えれば, 断面の長方形の和は各長方形の右上を保存しておけばよい.
この点列は内部に含まれるものを除けば階段状になっているので, 長方形を追加するときにすぐ下の段(右の段)にくる長方形は2分探索で求められる.
そこから1つずつ左に見ていき, 高さを積分していくことで増加分の面積を求める.
すぐ上の段を見つけたら間に今作った新しい段に完全に含まれる段を取り除く.
（中文概述）
首先我们现将鱼的身长 $p$ 从大到小排一下序，此时我们可以求出对于每一个 $i$ 它的极大三元组，就是对于每一个 $i$，求一个最大的 $j$，使得 $p_j<p_i*2$。那么统计 $i$ 到 $j$ 中的 $r, b, g$ 的个数，记它为极大三元组，我们记这 $n$ 个极大三元组为 $a, b, c$。显然，对于任意一个三元组 $(a’, b’, c’)$，只要满足 $a'<a, b'<b, c'<c$，答案就是合法的。
如果将 $a, b, c$ 放入立体三维空间中，那么问题就转换为了求 $n$ 个前缀正方体的体积并，我们把它转换为二维，问题就简单了很多。
添加一个新点的过程
首先我们将它们以 $a$ 从小到大排序，然后依次在平面内加入点 $(b, c)$，我们可以发现，对于任意 $a’>a$ 满足 $a’$ 的所有 $(b, c)$ 一定在 $a$ 下成立，所以每次在统计 $a$ 的时候，要加上之前 $>a$ 的面积并。并且我们发现，每一时刻面积并的形状都是阶梯状的，也就是说，$b$ 越大 $c$ 越小。我们每次加入一个点，用 $set$ 维护阶梯外沿这条折线的每一个拐角，统计新增的答案即可。
コード
#include
#define ll long long
#define maxn 500100
struct Thr{
int a,b,c;
Thr(int x=0,int y=0,int z=0){
a=x,b=y,c=z;
}
bool operator < (const Thr &x) const{
return a>x.a;
}
}d[maxn];
struct Fish{
int c,p;
Fish(int x=0,int y=0){
c=x,p=y;
}
bool operator < (const Fish &x) const{
return ps;
void Init(){
int sum[3]={0},top=0;
for (int i=1;i<=n;i++){
if (i>1) sum[a[i-1].c]--;
while(top=y) break;
tem+=1ll*(y-b[x].h)*(x-b[x].l);
b[x].h=y;
x=b[x].l;
}
x=d[i].b;
while(b[b[x].l].h==b[x].h){
int tx=b[x].l;
b[b[tx].l].r=b[tx].r;
b[b[tx].r].l=b[tx].l;
s.erase(tx);
}
}
ans+=1ll*tem*d[n].a;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;++i){
char s[1];
int x,b;
scanf("%d%s",&x,&s);
if (s[0]=='R') b=0;
if (s[0]=='G') b=1;
if (s[0]=='B') b=2;
a[i]=Fish(b,x);
}
std::sort(a+1,a+1+n);
Init();
std::sort(d+1,d+1+n);
Solve();
printf("%lld\n",ans-1);
return 0;
}