如果你TLE on #1 #2 #4 #6 #10

可能是你的线段树写炸了（虽然我也不知道为什么能过这么多点

具体来说，这份 $query$ 是错的

int query (int p, int l, int r, int L, int R)
{
    if (!p) return 0;
    if (L <= l && r <= R) return val (p);
    int mid = (l + r) >> 1;
    if (l <= mid && r <= mid) return query (ls (p), l, mid, L, R);
    else if (l > mid && r > mid) return query (rs (p), mid + 1, r, L, R);
    else return query (ls (p), l, mid, L, R) + query (rs (p), mid + 1, r, L, R);
}

应该是

int query (int p, int l, int r, int L, int R)
{
	if (!p) return 0;
	if (L <= l && r <= R) return val (p);
	int mid = (l + r) >> 1;
	if (L <= mid && R <= mid) return query (ls (p), l, mid, L, R);
	else if (L > mid && R > mid) return query (rs (p), mid + 1, r, L, R);
	else return query (ls (p), l, mid, L, R) + query (rs (p), mid + 1, r, L, R);
}