题解：

 

Code：

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;const int N=100010,M=1010,E=5500000,BUF=10000000,OUT=10000000;unsigned int SA,SB,SC;int Case,n,p,m,lim,X,i,j,k,op,x,y,a[N],g[N],nxt[N],st[N],en[N],dfn,s[N<<1],q[N];int b[M],cb,f[M][M],ga[N<<1],gq[N<<1],vl[E],vr[E],w[E],NXT[E],ED;ll ans[N<<1],bit[N<<1],bitx[N<<1],bity[N<<1],bitxy[N<<1];char Buf[BUF],*buf=Buf,Out[OUT],*ou=Out;int Outn[30],Outcnt;inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}inline void read(unsigned int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}inline void write(ll x){  if(!x)*ou++=48;  else{    for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;    while(Outcnt)*ou++=Outn[Outcnt--];  }}inline void writeln(ll x){write(x);*ou++='\n';}inline unsigned int rng61(){  SA^=SA<<16;  SA^=SA>>5;  SA^=SA<<1;  unsigned int t=SA;  SA=SB;  SB=SC;  SC^=t^SA;  return SC;}inline void addedge(int x,int y){nxt[y]=g[x];g[x]=y;}inline void add(int&x,int l,int r,int z){vl[++ED]=l;vr[ED]=r;w[ED]=z;NXT[ED]=x;x=ED;}void dfs(int x){  lim=st[x]=++dfn;  s[dfn]=1;  for(int i=g[x];i;i=nxt[i])dfs(i);  en[x]=++dfn;  s[dfn]=-1;}inline bool cmp(int x,int y){return a[x]
        
         lim)en[i]=lim;  }  sort(q+1,q+n+1,cmp);  for(i=1;i<=n;i=j){    b[0]=0;    b[cb=1]=lim;    for(j=i;j<=n&&a[q[i]]==a[q[j]];j++)solve(q[j],0);    initrect();    for(k=i;k
         
          0)ans[k]+=ask(vr[j])-ask(vl[j]-1);      else ans[-k]-=ask(vr[j])-ask(vl[j]-1);    }  }  for(i=1;i<=m;i++)writeln(ans[i]);}int main(){  fread(Buf,1,BUF,stdin);  read(Case);  while(Case--)work();  fwrite(Out,1,ou-Out,stdout);  return 0;}