大致题意： 一棵树，每个节点有一个人，他打水需要\(T_i\)的时间，每次询问两点之间所有人去打水的最小等待时间。

伪·强制在线

这题看似强制在线，但实际上，\(pre\ mod\ 2\)只能为\(0\)或\(1\)，因此只要将两种情况下的答案都求出来，最后视情况输出即可。

这样就可以用离线算法乱搞了。

树上莫队+树状数组

其实，这道题是可以用来做的。

考虑当前已有若干人要去打水，现在新加入一个人，他的打水时间为\(x\)，求改变的贡献值。

显然，根据贪心的思想，我们应让打水时间越久的人越早打水。

则设有\(rk\)个人打水时间\(>x\)，\(val\)为打水时间\(\le x\)的人打水时间总和，则这个人所需等待时间为\((rk+1)*x+val\)。

不难发现，\(rk\)和\(val\)两个值是可以用树状数组来进行维护的。

这样这题就做完了。

代码

#include
    
      #define N 50000 #define LL long long #define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y) #define swap(x,y) (x^=y^=x^=y) using namespace std; int n,query_tot,key,ee,a[N+5],lnk[N+5]; struct edge {     int to,nxt; }e[(N<<1)+5]; class Class_FIO {     private:         #define Fsize 100000         #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)         #define pc(ch) (void)(FoutSize
     
      >1;l<=r;mid=l+r>>1) data[mid]
      
       y.r);}         }q[(N<<1)+5];     public:         inline void Solve()         {             int i,x,y,z,k,s=1,t,v,L=1,R=0;LL res=0,lst_ans=0;             for(D.Init(),Di.Init(n,a),T.len=Di.cnt,S=sqrt(n),i=1;i<=query_tot;++i)//每个询问分pre%2的值存储两个            {                 if(F.readc(opt[i]),F.read(k),opt[i]^'Q') {s=k;continue;}                 D.I[x=k%n+1]>D.I[y=s]&&swap(x,y),q[++Q]=(z=D.LCA(x,y))^x?Query(D.O[x],D.I[y],i,0,bp(D.O[x]),z):Query(D.I[x],D.I[y],i,0,bp(D.I[x]),0);                 D.I[x=(k+key)%n+1]>D.I[y=s]&&swap(x,y),q[++Q]=(z=D.LCA(x,y))^x?Query(D.O[x],D.I[y],i,1,bp(D.O[x]),z):Query(D.I[x],D.I[y],i,1,bp(D.I[x]),0);             }             for(sort(q+1,q+Q+1),i=1;i<=Q;++i)//处理询问            {                 while(R
       
        q[i].l) F5(D.s[--L]);while(R>q[i].r) F5(D.s[R--]);while(L