题意：
给定长度为\(L\)，元素总和为\(S\)的非负整数序列\(A\)，对于每一个\(1 \leq i \leq S\)，求出：所有满足\(\sum_{j=l}^rA_j=i\)的二元组\((l,r)\)排序后的中位数。
二元组的比较方式：先比较\(l\)，小的在先；\(l\)相同比较\(r\)，小的在先。
\(1 \leq L , S \leq 30000\)
思路：
易见可以把二元组\((l,r)\)看作一个左端点落在\(l-1\)与\(l\)之间，右端点落在\(r\)与\(r+1\)之间的区间。
那么若连续\(c\)个零的下标为\(i\)到\(i+c-1\)，则一个区间的左/右端点落在\(i-1\)与\(i\)之间，或\(i\)与\(i+1\)之间，……，或\(i+c-1\)到\(i+c\)之间，不影响其总和。那么，我们可以把这\(c+1\)个落点合并为一个（不妨用\(i-1\)和\(i\)之间的那个来代表），并给它标上权值\(c+1\)，意味着如果一个区间选取它为端点，就会产生另外\(c\)个与之相同的区间。
同样的，我们把一个非零元素\(a\)拆成\(a-1\)个权值为0的落点和随后紧邻的1个权值为1的落点。可以认为，任何区间都不能以权值为0的落点作为端点。
来自不同元素的落点，按照原先元素的顺序排列。
这样做的意义在于，经过变换之后，区间\([i,j]\)（其中\(i\)和\(j\)是变换之后落点的编号）在序列\(A\)的总和为\(j-i\)，且共有\(m_i \cdot m_j\)个与之完全相同的区间，其中\(m_i\)是落点\(i\)的权值。
hint：对于零元素落点的合并操作，注意到\(i-1\)与\(i\)之间的落点，实际上就是前一个非零元素拆成的最后一个落点，所以合并时直接执行\(m_{last}\)+=\(c\)即可。
看到这里，有没有嗅到一股法法塔的气息！！！
对\(m\)序列求得卷积序列\(cnt\)，满足：
\]
而\(cnt_i\)就是\(A\)数组中总和为\(i\)的连续子序列数量！
这样可以求出对每一个\(i\)，二元组\((l,r)\)的数量，进而可以知道（对每一个\(i\)）二元组排序后中位数的下标。
知道下标之后，就是常规操作了。注意到如果把\(m\)与自己的一个前缀做卷积，得到的\(cnt_i\)，就是\(A\)中总和为\(i\)，且左端点下标不超过\(k\)的区间数量，这里的\(k\)是与\(m\)前缀的长度正相关的一个值。
对于每一个\(i\)，可以对所求二元组的左端点二分答案，并每次用前缀卷积得到的\(cnt_i\)判断。但是直接暴力做会超时，整体二分又用不了（单轮check的复杂度只与\(L\)相关，不满足使用整体二分的条件），所以考虑分块。
把\(m\)序列分成大小为\(\sqrt[2]{L \cdot \log L}\)的块，并通过\(O(\sqrt[2]{\frac{L}{\log L}})\)次卷积，确定对每一个\(i\)，其所求二元组的\(l\)在哪一块里。
最后对每一个\(i\)，在块内暴力找到准确的左端点和右端点即可。记得把\(m\)序列中的下标映射回到\(A\)序列中去。
复杂度\(O(L \cdot \sqrt[2]{L \cdot \log L})\)。
代码：
#include<iostream>
#include<cstdio>
#include<ctime>
#include<vector>
#include<cstring>
using namespace std;
#define iinf 2000000000
#define linf 1000000000000000000LL
#define ulinf 10000000000000000000ull
#define MOD1 1000000007LL
#define mpr make_pair
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned long UL;
typedef unsigned short US;
typedef pair < int , int > pii;
clock_t __stt;
inline void TStart(){__stt=clock();}
inline void TReport(){printf("\nCurrent Case Taken Time : %.3lf sec\n",(double)(clock()-__stt)/CLOCKS_PER_SEC);}
template < typename T > T MIN(T a,T b){return a<b?a:b;}
template < typename T > T MAX(T a,T b){return a>b?a:b;}
template < typename T > T ABS(T a){return a>0?a:(-a);}
template < typename T > void UMIN(T &a,T b){if(b<a) a=b;}
template < typename T > void UMAX(T &a,T b){if(b>a) a=b;}
const LL MODG=998244353,G=3;
int powM(int num,int pw,LL moD=MODG){
int ret=1;
while(pw){
if(pw&1) ret=((LL)ret*(LL)num)%moD;
num=((LL)num*(LL)num)%moD;
pw>>=1;
}
return (int)ret;
}
int n,s,rk[30005],lv[30005],a[30005],v[60005],ln,ld[60005],pcnt[60005],cnt[140005],A[140005],B[140005];
int SZ,SZINV,BUC;
void ntt(int *a,int l,bool r){
int i,j=l/2,k;
for(i=1;i<l;++i){
if(i<j) swap(a[i],a[j]);
for(k=l/2;j&k;k>>=1) j^=k;
j^=k;
}
for(i=1;(1<<i)<=l;++i){
int cl=(1<<i);
int w=powM(G,(MODG-1)/cl);
if(r) w=powM(w,MODG-2);
for(j=0;j*cl<l;++j){
int cur=1;
for(k=0;k<(cl>>1);k++){
int v1=a[j*cl+k],v2=((LL)a[j*cl+k+(cl>>1)]*(LL)cur)%MODG;
a[j*cl+k]=(v1+v2)%MODG;
a[j*cl+k+(cl>>1)]=(v1-v2+MODG)%MODG;
cur=((LL)cur*(LL)w)%(LL)MODG;
}
}
}
}
void getcnt(int pre){
int i,j,k;
memset(A,0,sizeof(int)*(SZ+5));
memset(B,0,sizeof(int)*(SZ+5));
memset(cnt,0,sizeof(int)*(SZ+5));
for(i=0;i<ln;++i){
A[i]=v[i];
}
ntt(A,SZ,0);
for(i=0;i<pre;++i){
B[ln-1-i]=v[i];
}
ntt(B,SZ,0);
for(i=0;i<SZ;++i){
A[i]=((LL)A[i]*(LL)B[i])%MODG;
}
ntt(A,SZ,1);
for(i=0;i<SZ;++i){
if(i+1-ln>=0){
cnt[i+1-ln]=((LL)A[i]*(LL)SZINV)%MODG;
}
}
}
void solve(){
// inputting start
// 数据结构记得初始化！ n，m别写反！
int i,j,k;
scanf("%d",&n);
s=0;
for(i=0;i<n;++i){
scanf("%d",a+i);
s+=a[i];
}
#ifdef LOCAL
TStart();
#endif
// calculation start
// 数据结构记得初始化！ n，m别写反！
ln=v[0]=1;
ld[0]=-1;
for(i=0;i<n;++i){
if(a[i]>0){
for(j=0;j<a[i]-1;++j){
ld[ln]=i;
v[ln++]=0;
}
ld[ln]=i;
v[ln++]=1;
}
else{
for(j=i;j<n && a[j]==0;++j) ++v[ln-1];
i=j-1;
}
}
for(BUC=2;BUC*BUC<ln*60;++BUC);
for(SZ=4;SZ<ln*2;SZ<<=1);
SZINV=powM(SZ,MODG-2);
getcnt(ln);
for(i=1;i<=s;++i){
rk[i]=(cnt[i]+1)/2-1;
lv[j]=-1;
}
for(i=0;i<=ln;i+=BUC){
getcnt(i);
for(j=1;j<=s;++j){
if(cnt[j]<=rk[j])
lv[j]=i;
else if(lv[j]==i-BUC)
rk[j]-=pcnt[j];
}
memcpy(pcnt,cnt,sizeof(int)*(s+3));
}
LL resL=0,resR=0;
for(i=s;i>=1;--i){
while(rk[i]>=v[lv[i]+i]*v[lv[i]]){
rk[i]-=v[lv[i]+i]*v[lv[i]];
++lv[i];
}
if(rk[i]>=0) resL+=(LL)(ld[lv[i]]+2+rk[i]/v[lv[i]+i]);
if(rk[i]>=0) resR+=(LL)(ld[lv[i]+i]+rk[i]%v[lv[i]+i]+1);
resL=(resL*233LL)%MOD1;
resR=(resR*233LL)%MOD1;
}
printf("%d %d\n",(int)resL,(int)resR);
#ifdef LOCAL
TReport();
#endif
}
int main(){
int t;
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}