题目:https://www.luogu.org/problem/show?pid=1565

原题解似乎是 $O(n^3 * \log n)$ 的

但这题有$ O(n^3) $的做法。

虽然 https://www.luogu.org/record/show?rid=2494227 我这个$ O(n^3*\log n) $的做法跑的比我的$ O(n^3) $还快。。(应该是数据问题)

就是枚举上下边界$ x_1 $,$ x_2 $，然后枚举右端点 $ i $，

那么就是求最左的点 $ j $ 满足 $ sum_j < sum_i $ ( $ sum_i $ 表示 $ x=x_1...x_2,\,y=0...i $ 这个矩形的面积和)

如果 $ j_1 < j_2 $ 且 $ sum_{j_1} < sum_{j_2} $ ，那么 $j_2 $ 不可能成为左端点。

所以可以用单调栈维护可能的左端点，查询时二分。

$ O(n^3) $的做法:

(1) https://www.luogu.org/record/show?rid=2498503

枚举上下边界，实际上不只是可能的左端点在单调栈上，可以同理证明可能的右端点在相反的单调栈上。

从左到右枚举右端点(只枚举单调栈上的)，左端点的变化是单调的。于是可以$ O(n) $

(2) https://www.luogu.org/record/show?rid=2498807

感觉这是理论最快的做法。

原理是:当上下区间长度不变时 就是要求左右区间长度的最大值 $ mx $ , 而 $mx$ 最多变大 $ n $ 次。

长度从大到小地枚举上下边界(其实从小到大也一样)，再枚举右端点 $ i $ ，

如果以$i$为右端点的区间长度的最大值大于当前的$ mx $ ,那么 $ sum_i>min\,\, sum_j | j=[0,i-mx] $，这两者等价

所以维护这个$min$，如果发现$sum_i>min$，就++$ mx $，之后暴力重新$ O(n) $算出 $ min $。

如果上下区间长度从大到小枚举，其实长度不变或变小时都不用修改$mx$，于是最多重算$O(n)$次$min$。

从小到大枚举的话，当长度变大时需要将$mx$清0，于是最多重算$O(n^2)$次$min$。

总之总复杂度都是$O(n^3)$

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=l;i<=r;++i)
template<class T>inline void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}
template<class T>inline void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
typedef long long ll;
const int N=205;
ll s[N][N];
int ans;
ll a,_a;int w,_w;
#define get(y) (s[x2][y]-s[x1][y])

int main()
{
    freopen("1.in","r",stdin);freopen("2.out","w",stdout);
    int n,m;
    cin>>n>>m;
    rep(i,1,n)
    {
      rep(j,1,m)
      { 
        scanf("%lld",s[i]+j);
        s[i][j]+=s[i][j-1];
      }
      rep(j,1,m)
        s[i][j]+=s[i-1][j];
    }
    int mx=1;
    for(int t=n;t;--t)
    {
        int x1=0,x2=t;
      do
      {
          int i=mx;ll mn=0;//mn=min(get(0)..get(i-mx))
         do
         {
             chmin(mn,get(i-mx));
           while(get(i)>mn&&mx<=i)
           {++mx;
            mn=0;
            rep(j,1,i-mx) chmin(mn,get(j));
           }
         }while(++i<=m);
      }while(++x1,++x2<=n);
       chmax(ans,t*(mx-1));
    }
    printf("%d\n",ans);
}

题目:https://loj.ac/problem/6003

贪心就是从小到大枚举编号，

之后在已经有球的柱子里随便找一个能放的放。

如果找不到，就新开一个柱子。

这个方法能通过本题。

但它是正确的吗？为什么？

(虽然看到网上已经有人问了，但没看到解答)

迟了半个小时多才ak。。

我打的dp似乎是O(n^5)的(不过常数挺小的)，应该不是最优的

考虑到距离序列

一定是一段一段的

每段每个点都向上一段连一条边，并可能存在段内互连

用dp[x][y1][y2][n1][n2]表示做到第x个点，上一段有y1个点还能连1条边,y2个点2条，当前段有n1个点1条，n2个点2条。

当y1=y2=0时，考虑把这个点新开一段

枚举他和当前段连的是2条的点还是1条的点

否则把这个点作为当前段

枚举他和上个段连的是2条的点还是1条的点

并枚举他和当前段内的连边

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=52,D=1e9+7,W1=50,W2=50*50,W3=50*50*50,W4=50*50*50*50;
int n;
int d[N];ll c[N][N];
map<int,int>f[N];

int dp(int x,int y1,int y2,int n1,int n2)
{
    if(y1<0||y2<0||n1<0||n2<0)return 0;
    if(x>n) return y1==0&&y2==0&&n1==0&&n2==0;

    int now=y1*W3+y2*W2+n1*W1+n2;
    if(f[x].count(now)) return f[x][now];

    ll ans=0;
    if(y1==0&&y2==0)
    {
        rep(x1,0,1)
        {
           int x2=1-x1;
           ans+=c[n1][x1]*c[n2][x2]%D*dp(x+1,n1-x1+x2,n2-x2,d[x]-x1-x2==1,d[x]-x1-x2==2);
        }
    }
    else
    {
        rep(x1,0,1)
        {
         int x2=1-x1;
        if(y1-x1+x2>=0&&x2<=y2)
        {
           int nd=d[x]-x1-x2;
           rep(nx1,0,nd)
           rep(nx2,0,nd-nx1)
            ans+=c[y1][x1]*c[y2][x2]%D*c[n1][nx1]%D*c[n2][nx2]%D*
            dp(x+1,y1-x1+x2,y2-x2,n1-nx1+nx2+(nd-nx1-nx2==1),
                                  n2-nx2+(nd-nx1-nx2==2));
        }
        }
    }
    return f[x][now]=ans%D;
}

int main()
{
    freopen("1.in","r",stdin);
    scanf("%d",&n);
    rep(i,1,n)scanf("%d",d+i);
    rep(i,0,n)
    {
       c[i][0]=1;    
       rep(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%D;
    }
    printf("%d\n",dp(3,d[1]==2,d[1]==3,d[2]==2,d[2]==3));
}

打了这么久，好像第一次rank1啊

t1

我打的50分dp

不过好像加常数优化后可以拿60-70分(我拿了60)

t2

f[i]表示gcd(边权)是i的倍数的方案数

如果把f[i]搞出来了，那么就可以nlogn求出答案。

f[i]其实就是矩阵树n^3求啊

不过加一个，如果不连通就直接退出

我也不会算复杂度

t3

一开始想打fwt拿50分，不知道为什么拿了40

后来想到，就枚举i,j和n,m的二进制的最长公共前缀

之后就可以搞了

t4

就是max-min=r-l

且不存在重复的数

把每对相邻重复的数l,r

以r为下标放到线段树里

就可以了

t5

分治

对两边所有不同的gcd,or暴力枚举

似乎是nlog^3的

但跑的挺快。。

t6

一开始把那个o(N)的方法看了一遍

后来发现构建笛卡尔树空间会开不下

分块 块间st+前后缀min是可以o(1)的

但询问在块内怎么办呢

答案就是块内直接暴力(因为随机，假设块大小为k，那么复杂度就是k/n n k=k * k)

upd:

t5复杂度是nlog的

t4 fwt中间没有取模 爆了long long 加了后拿到50分

两道题我都不知道有没有更优做法。。

https://daniu.luogu.org/problem/show?pid=3591

如果步长>根号的话，

步数就<根号，

直接暴力模拟每一步就可以了。

如何暴力模拟？

求出lca，问题就只剩下如何求一个点距离为k的祖先。

就是按size链剖，每条链记录每个深度的点。

找距离为k的祖先，如果当前这条链不够，就跳到下一条链。

这样最多一次询问只会跳log条链，时间是根号的。

(其实这个问题17年集训队论文里讲了梯子+倍增的O(1)做法，不过这题我这样做也就已经均摊O(1)了)

如果步长<根号的话，

我们就对每个这样的步长k特殊处理，那么也只用处理根号次。

就是dp出每个点距离为k的祖先，并处理出i,i-k,i-k*2...点权的前缀和。

询问时找到最浅那个i-k*x就可以了。

dp时间也是n根号的。

总时间n根号。

https://www.luogu.org/problem/show?pid=3751

对每个询问暴力模拟，时间应该是k[x]+k[y]的。

也就是每次选一个离下一个点较近的移动，之后判一下是不是起点的相对前后!=终点的相对前后。

如果k[x],k[y]都<根号，那么这是没问题的。

如果k[x],k[y]都>根号，那么记忆化一下，应该也是没问题的。

否则，如果我们能用较小的k的时间，那么也是ok的。

因为速度是一样的，所以x移动一次最多只会相遇一次，而且相对前后一旦变了就变不回去了。

所以只要每次移动x，之后二分一下y会移动到哪里就可以了。

时间O(n根号log)

我只想到了n根号(nlog)log的分块，感谢出题人教了我如何n根号log。

(假设分k块)

每个块内都排好序。

加的时候
整块的就打标记 O(k)
零散的，
考虑打标记后，没打标记的和打了标记的部分顺序都还是不变，
遍历一遍原来排好的顺序，就能得到这两个部分，之后归并一下就可以了。O(n/k)

求k大
先二分 转为check一个区间有多少数比一个数小。

按普通的想法
整块的二分 O(klog)
零散的暴力 O(n/k)
所以一次复杂度是O(klog^2+nlog/k)
k取根号(n/log),总复杂度就是O(n根号(nlog)log)

注意到，check零散的时间是O(nlog/k)，这还可以优化。
首先，用遍历一遍原来顺序的方法 O(n/k)把两个零散的各自排序。
之后check的时候就可以二分了，O(log^2)
所以一次复杂度变成O(klog^2+n/k)
k取根号n/log,总复杂度就是O(n根号nlog)

还有一个方法，是跟值域有关的。

因为值域小了，就可以处理出每个块的前缀和

分块使得
1 每个块max-min<=x1*len
2 块的大小也不超过x2
3 块尽量大

如果不考虑2的话 块是n/x1个的
因为所有相邻两数的差的和是nlen的 因为n次区间加，每次加len
而相邻两块的max-min>x1len
说明相邻两块所有相邻两数的差>max-min>x1len
所以块数<nlen/x1*len=n/x1

现在再把2考虑进来 相当于说一些大于x2的块要被拆掉
设大于x2的块的大小-x2的和是sum 那么每拆一次 sum-=x2
所以最多拆n/x2次

所以块数是n/x1+n/x2的。
因为所有块max-min的和<nlen，所以build的时间是nlen

check的时候
整块就可以O(1)
零散的暴力 就是x2
时间O(log*(n/x1+n/x2+x2))

加的时候整块打标记，O(n/x1+n/x2)
零散的暴力重算块的前缀和,O(x2+x1*len)

注意根号次加法后，块的max-min可能又大了根号*len，

这个时候要再重构一次分块。

时间(根号nlen)

x1,x2应该都要取根号

总时间O(n根号log+n根号len)

因为感觉第一种比较好写 我只写了第一种

#include<bits/stdc++.h>
using namespace std;

#define mid (l+r>>1)

const int ch_top=10000000;
char ch[ch_top],*now_r=ch,*now_w=ch-1;
int read()
{
    while(*now_r<'0')++now_r;
    int x=*now_r-'0';
    while(*++now_r>='0') x=x*10+*now_r-'0';
    return x; 
}
void write(int x)
{
    static char st[20];static short top;
    if(!x)*++now_w='0';
    else
    {
        for(;x;x/=10)st[++top]='0'+x%10;
        for(;top;--top)*++now_w=st[top];
    }
    *++now_w='\n';
}

const int N=100005,L=1500,K=N/L+5;
int f[N],w[N];vector<int>son[N];
typedef vector<int>::iterator ii;
int a[N],b[N];//b[i]是块排好序后的人 

int q[N],t,qa[N],la,qb[N],lb;
void merge_to(int *q)
{
    if(!lb) { memcpy(q+1,qa+1,la*sizeof(int));return ; }
    if(!la) { memcpy(q+1,qb+1,lb*sizeof(int));return ; }
    t=0;
    int ha=1,hb=1;
    for(;;)
    if(a[qa[ha]]<a[qb[hb]])
    {
        q[++t]=qa[ha];
        if(++ha>la) 
        {
            do
            {
                q[++t]=qb[hb];
            }while(++hb<=lb);
            break;
        }
    }
    else
    {
        q[++t]=qb[hb];
        if(++hb>lb) 
        {
            do
            {
                q[++t]=qa[ha];
            }while(++ha<=la);
            break;
        }
    }
}

int kl[K],kr[K],ad[K];
bool a_xiao(int x,int y)
{
    return a[x]<a[y];
}

void chmin(int &x,int y)
{
    if(x>y)x=y;
}
void chmax(int &x,int y)
{
    if(x<y)x=y;
}

int dfn[N],out[N],tot;
void dfs(int x,int fr,int now)
{
    now+=w[x];
    a[dfn[x]=++tot]=now;
    for(ii it=son[x].begin();it!=son[x].end();++it)
     dfs(*it,x,now);
    out[x]=tot;
}

int nl,nr;
int erfen(int *q,int t,int now)
{
    if(a[q[1]]>now)return 0;
    if(a[q[t]]<=now)return t;
    int l=1,r=t;
    while(l+1!=r)
    if(a[q[mid]]<=now) l=mid;
    else r=mid;
    return l;
}
int xiao_deng(int now)
{
   int ans=erfen(qa,la,now)+erfen(qb,lb,now);
   for(int k=nl+1;k<nr;++k) ans+=erfen(b+kl[k]-1,L/*kr[k]-kl[k]+1*/,now-ad[k]);
   return ans;
} 

void down(int k)
{
    int x=ad[k];
    if(!x)return ;
    for(int i=kl[k];i<=kr[k];++i) a[i]+=x;
    ad[k]=0;
}

int main()
{
    //freopen("1.in","r",stdin);freopen("3.out","w",stdout);
    ch[fread(ch,1,ch_top,stdin)]=0;
    int n=read(),m=read(),i,k;
    read();
    for(i=2;i<=n;++i)
    {
        son[f[i]=read()].push_back(i);
        w[i]=read();
    }

    dfs(1,0,0);

    tot=(n-1)/L;
    for(i=0;i<=tot+1;++i) {kl[i]=i*L+1;kr[i]=(i+1)*L;}
    kr[tot]=n;

    for(i=1;i<=n;++i)b[i]=i;
    for(k=0;k<=tot;++k)
        sort(b+kl[k],b+kr[k]+1,a_xiao);

    while(m--)
    {
        int type=read(),x=read();
        int ql=dfn[x],qr=out[x]; 
        //int ql=read(),qr=read();
        x=read();
        nl=(ql-1)/L;nr=(qr-1)/L;
        if(type==1)
        {
            int len=qr-ql+1;
            if(len<x) { *++now_w='-';*++now_w='1';*++now_w='\n';continue; }  
            down(nl);down(nr);
            if(len<=L*2)
            {
                down(nl+1);
                memcpy(q,a+ql,len*sizeof(int));
                nth_element(q,q+x-1,q+len);
                write(q[x-1]);
                continue;
            }
            else
            {
                la=0;
                for(i=kl[nl];i<=kr[nl];++i)
                if(b[i]>=ql) qa[++la]=b[i];
                lb=0;
                for(i=kl[nr];i<=kr[nr];++i)
                if(b[i]<=qr) qb[++lb]=b[i];
                //merge_to(q);

                int l=min(a[qa[1]],a[qb[1]]),r=max(a[qa[la]],a[qb[lb]]);
                for(k=nl+1;k<nr;++k) 
                {
                  chmin(l,a[b[kl[k]]]+ad[k]);
                  chmax(r,a[b[kr[k]]]+ad[k]); 
                }
                if(xiao_deng(l)>=x) { write(l);continue; }
                while(l+1!=r)
                {
                    if(xiao_deng(mid)>=x) r=mid;
                    else l=mid;
                }
                write(r);
            }
        }
        else
        {
            if(nl==nr)
            {
                for(i=ql;i<=qr;++i) a[i]+=x;
                la=lb=0;
                for(i=kl[nl];i<=kr[nl];++i) 
                if(b[i]>=ql&&b[i]<=qr) qa[++la]=b[i];
                else qb[++lb]=b[i];
                merge_to(b+kl[nl]-1);
                continue;
            }
            for(k=nl+1;k<nr;++k) ad[k]+=x;

            for(i=ql;i<=kr[nl];++i) a[i]+=x;
            la=0;lb=0;
            for(i=kl[nl];i<=kr[nl];++i)
            if(b[i]>=ql) qa[++la]=b[i];
            else qb[++lb]=b[i];
            merge_to(b+kl[nl]-1);

            for(i=kl[nr];i<=qr;++i) a[i]+=x;
            la=0;lb=0;
            for(i=kl[nr];i<=kr[nr];++i)
            if(b[i]<=qr) qa[++la]=b[i];
            else qb[++lb]=b[i];
            merge_to(b+kl[nr]-1);
        }
    }
    fwrite(ch,1,now_w-ch+1,stdout);
}

简要题意:
区间众数 强制在线 空间<n根号

区间众数的做法很普通
就是分根号块 预处理两块之间众数mx[i][j]，以及cnt[i][j]表示前i块中权值j出现次数
询问时要么众数是块间原本的众数 否则一定在多出来的里面出现过 时间n根号
由于cnt[i][j] 空间n根号

如何优化空间呢

特判掉出现次数<k的权值 这样cnt[i][j]中j就<=n/k 空间就变成n根号/k了

怎么特判呢 就是再用个l[k][i]表示出现次数=k时，右端点为i，第一次可以的那个左端点(也就是最大的那个)

我k取了3 (由于初始ans为清0，导致第一次就异或，wa了很久很久)

#include<cstdio>
#include<algorithm>
#include<string.h>
using std::sort;
using std::swap;

#define us unsigned short
#define gc getchar()
void read(us &x)
{
    char ch;
    while((ch=gc)<'0');
    for(x=ch-'0';(ch=gc)>='0';)x=x*10+ch-'0';
}
void read(int &x)
{
    char ch;
    while((ch=gc)<'0');
    for(x=ch-'0';(ch=gc)>='0';)x=x*10+ch-'0';
}

void chmax(us &x,us y)
{
    if(x<y)x=y;
}

#define B(i) ((i-1)/len)
const int K=240,N=60000,U=N/4+5;
us kl[K],kr[K];
us cnt[K][U],mx[K][K];
us n,m,i,j,l,len,k;
us a[N+5],top;bool del[N+5];
us now[U],st[N/K*2+10],stt,nowmx;
us dr[N+5],dl[N+5];
us l_2[N+5],l_3[N+5];//l_i[r]= 当右端点=[1,r]时，达到i需要的最大左端点 

struct item
{
    int a;us id;
    bool operator <(const item &i)const
    {
        return a<i.a;
    }
}q[N+5];
void mark(us l,us r)
{
    if(l>r)swap(l,r);
    del[l]=del[r]=1;chmax(l_2[r],l);
}
void mark(us a,us b,us c)
{
if(a>b)swap(a,b);
if(b>c)
{swap(b,c);
if(a>b)swap(a,b);
}
    del[a]=del[b]=del[c]=1;
    chmax(l_3[c],a);
    chmax(l_2[c],b);
    chmax(l_2[b],a);
}
void check(us i)
{
    if(i==1||(q[i].a!=q[i-1].a)) 
    {    
        del[q[i].id]=1; 
        --top;
    }else
    if(i==2||(q[i].a!=q[i-2].a)) 
    {
        mark(q[i].id,q[i-1].id); 
        --top;
    }else
    if(i==3||(q[i].a!=q[i-3].a))
    {
        mark(q[i].id,q[i-1].id,q[i-2].id);
        --top;
    }
}
void lisan()
{
    for(i=1;i<=n;++i){read(q[i].a);q[i].id=i;}
    sort(q+1,q+n+1);
    top=a[q[1].id]=0;
    for(i=2;i<=n;++i)
    {
     if(q[i].a!=q[i-1].a) 
     {
       check(i-1);++top;
     }
     a[q[i].id]=top;  
    }
    check(n);
}

void write(us x)
{
    putchar('-');
    for(;x;x/=10)st[++stt]=x%10;
    for(;stt;--stt)putchar('0'+st[stt]);
    putchar('\n');
}

us ql,qr,L,R;

int main()
{   freopen("1.in","r",stdin);freopen("2.out","w",stdout);
    read(n);read(m);
    lisan();

    us t=0;
    for(i=1;i<=n;++i)
    {
        if(del[i])dr[i]=t;
        else a[dr[i]=++t]=a[i];
    }
    dl[n+1]=++t;
    for(i=n;i;--i)
    {
        if(del[i])dl[i]=t;
        else dl[i]=--t;
    }
    t=dr[n];
    for(i=1;i<=n;++i) {chmax(l_2[i],l_2[i-1]);chmax(l_3[i],l_3[i-1]);}

    if(!t)
    {
        while(m--)
        {
            read(ql);read(qr);
                ql^=nowmx;qr^=nowmx;
            nowmx=(ql<=l_3[qr])?3:((ql<=l_2[qr])?2:1);
            write(nowmx);
        }
        return 0;
    }

    for(len=1;B(t)>=K||len<t/len;++len);
    kl[0]=1;
    for(i=len+1;i<=t;i+=len) {kr[B(i)-1]=i-1;kl[B(i)]=i;} 
    kr[k=B(t)]=t;

    for(i=0;i<=k;++i)
    {
        nowmx=0;
        for(j=i;j<=k;++j)
        {
          for(l=kl[j];l<=kr[j];++l)
          if(++now[a[l]]>nowmx)nowmx=now[a[l]];
          mx[i][j]=nowmx;
          if(!i)memcpy(cnt[j],now,(top+1)*2);
        }
        memset(now,0,(top+1)*2);
    }

    nowmx=0;
    while(m--)
    {
        read(ql);read(qr);
        ql^=nowmx;qr^=nowmx;
        L=B(dl[ql]);R=B(dr[qr]);
        if(L>=R) 
        {
            for(i=dl[ql];i<=dr[qr];++i)
            if(++now[a[i]]==1) st[++stt]=a[i];
            nowmx=0;
            for(;stt;--stt) 
            {
              if(now[st[stt]]>nowmx)nowmx=now[st[stt]];
              now[st[stt]]=0;
            }
        }
        else
        {
            for(i=dl[ql];i<=kr[L];++i)
            if(++now[a[i]]==1) st[++stt]=a[i];
            for(i=kl[R];i<=dr[qr];++i)
            if(++now[a[i]]==1) st[++stt]=a[i];
            nowmx=mx[L+1][R-1];
            for(;stt;--stt) 
            {
              us &x=now[st[stt]];
              x+=cnt[R-1][st[stt]]-cnt[L][st[stt]];
              if(x>nowmx)nowmx=x;
              x=0;
            }
        }
        if(nowmx<3)
        {
         if(ql<=l_3[qr])nowmx=3;
         else
         if(nowmx<2)
         {
           if(ql<=l_2[qr])nowmx=2;
           else
           if(nowmx<1)nowmx=1; 
         }
        }
        write(nowmx);
    }
}

s是c的后缀，倒过来，s就是c的前缀。

之后建trie树，所有c就是s的子树。

所以问题就转化了求子树k大。

由于可以离线，所以可以把询问挂在节点上。

dfs一遍，用直接转移重儿子,暴力轻儿子的方法维护当前的权值线段树，时间O(nlog^2)。

有了权值线段树，询问时只用O(log)。

感觉会比主席树快，没试过。

加了fread,fwrite后拿了rank1

#include<bits/stdc++.h>

#define gc getchar()
int read()
{
    char ch;
    while((ch=gc)<'0');
    int x=ch-'0';
    while((ch=gc)>='0')x=x*10+ch-'0'; 
    return x;
}

const int N=100005,T=300005;
int dy[N],j;
int ch[T][26],tot=1;
int cnt[T],t[T],next[N];
int sz[T],dfn[T],out[T],q[N],son[T];
int k[N],ans[N];

int a[N*3],d;
void clear(int i)
{
    for(i+=d;i;i>>=1)--a[i];
}
void add(int i)
{
    for(i+=d;i;i>>=1)++a[i];
}
#define L (i<<1)
int qiu(int k)
{
    if(k>a[1]) return -1;
    int i=1;
    while(i<=d)
    if(k<=a[L])i=L;
    else { k-=a[L];i=L+1; }
    return i-d;
}

char s[T];int len;
int to(int &x)
{
    if(!x)x=++tot;
    return x;
}

void dfs(int x)
{
    dfn[x]=tot+1;
    int i,y;
    for(i=t[x];i;i=next[i]) q[++tot]=i;

    for(i=0;i<26;++i) 
    if(y=ch[x][i]) 
    {
        dfs(y);
        if(sz[y]>sz[son[x]]) son[x]=y;
    }

    sz[x]=(out[x]=tot)-dfn[x]+1;
}
void solve(int x)
{
    int i,y,c=son[x];
    if(sz[c])
    {
        for(i=0;i<26;++i)
        if((y=ch[x][i])!=c&&sz[y]) 
        {solve(y); 
         for(j=dfn[y];j<=out[y];++j) clear(q[j]);
        }
        solve(c);
        for(j=dfn[x];j<dfn[c];++j) add(q[j]);
        for(j=out[x];j>out[c];--j) add(q[j]);
    }
    else 
    for(j=dfn[x];j<=out[x];++j) add(q[j]);

    for(j=0;j<cnt[x];++j)
    {
        i=q[dfn[x]+j];
        ans[i]=qiu(k[i]);
    }
}

int main()
{

    int n=read(),i,now,x;
    for(i=1;i<=n;++i)
    {
        scanf("%s",s+1);len=strlen(s+1);
        now=1;
        for(j=len;j;--j) now=to(ch[now][s[j]-'a']);
        ++cnt[dy[i]=now];
        next[i]=t[now];t[now]=i;
    }
    for(i=1;i<=n;++i) k[i]=read();

    for(d=1;d<n;d*=2);d-=1;
    tot=0;
    dfs(1);
    solve(1);

    for(i=1;i<=n;++i) printf("%d\n",ans[i]);
}

第一次参加zjoi，30+30。我果然太弱了。

感觉这应该是很长一段时间里对我最重要的比赛了，还是记录一下吧。

day1

是在我们学校的。

看到第一题觉得可以dp 之后就花了大概3个小时想了现在也不知道对不对的dp

后来虽然过了很小数据的对拍，但忘了测大样例

最后也只有20分

第三题本来想打30分，但fft有点记不清了，后来就打了10分。

第二题我没发现他就是个单点修改，后缀求和。

不知道他在干什么，然后就在最后快没时间的时候想打个10分，结束时还差个逆元没打，所以就0分了。

龙爷t2发现了那个性质，似乎拿了70分。

day2

t1，我想先把n-1块看成一块，假如得到了他移动的代价，

之后就记忆化搜索搜出来他和第n块一起移动的代价。

但我没考虑到移动的过程是先颠倒在最后才达到目标的。

最后拿了10分。

不少人推出了k=2时如何移动，拿了40分。

t2，我就打了20分。先把询问的人在线段树走一遍打上标记，之后把[l,r]走一遍，走的时候顺便得到lca。

龙爷想了个O(nlog^2)的做法，

就是发现如果一个左端点被区间[l,r]覆盖，那么l<=他的l，r>=他的r且r<他爸爸的r。

而求的东西类似带权距离和，是可以用点分树做的。

那么这题就是个矩形修改单点询问。

枚举右端点，线段树套点分树维护左端点。

然而实际上常数较大，很难跑过去，最后也只拿了10分。。。。。

以为稳进队的龙爷就这样挂了。

第三题我随便打了个线段树维护区间最小后缀，比较两个后缀的时候用二分lcp，线段树维护hash来检验的方法。

不知道怎么支持区间加，所以也不知道怎么才能拿随机和10^4的分(现在还是不知道这两个部分分什么意思)

但没修改是nlog^2的，以为30分总有的吧。

然而会t。原因大概是我觉得数值太大，hash有点虚，于是用了3个取模的hash。

如果用后缀数组初始化复杂度就是nlogn+mlog^2，应该就没问题了。但我也没时间打了。

特别厉害的sjj学长也没能进队。

zjoi怎么这么难啊。

点分，处理每个点到根的bitset，询问时或一下两个bitset。

但是由于可持久化树存储的bitset或运算会很慢，在q*n/32本来就是时间瓶颈的情况下显然是不好的，

所以我想不用可持久化bitset，而是直接每个点都新开个bitset。

注意到实际上bitset只用当前分治处理的这棵树的信息，所以离散化一下，大小就变成O(树的大小)了

于是复杂度就是O(n^2/32+n^2/2/32+..n^2/n/32)=O(n^2/32)。

于是我没有把int全部替换成unsigned short，也没有在分治的树小的时候暴力等等，就拿到了bzoj rank1。

#include<bits/stdc++.h>
using std::sort;

#define us unsigned short
#define ui unsigned int
const int N=40010;
struct edge
{
    int to,next;
}l[N<<1];int e;
int a[N],t[N];

int n,i,x,y;
bool xiao(int *x,int *y)
{
    return *x<*y;
}
void lisan()
{
    static int *q[N],top;
    for(i=1;i<=n;++i)q[i]=a+i;
    sort(q+1,q+n+1,xiao);
    int now=-1;
    for(i=1;i<=n;++i)
    {
        if(*q[i]!=now){now=*q[i];++top;}
        *q[i]=top;
    }
}

us t_f[N],deep[N];
ui *b[17][N],**now_b,*X,*Y;
us U[N];

bool vis[N];
us q[N],head,tail,sz[N];
us cnt[N],mx;
us f[N];
void build(us rt,us dep,us fr)
{
    for(;mx;--mx)cnt[mx]=0; 
    f[q[tail=1]=rt]=0;
    for(head=1;head<=tail;++head)
    {
        x=q[head];sz[x]=1;
        cnt[a[x]]=1;if(a[x]>mx)mx=a[x];
        for(i=t[x];y=l[i].to;i=l[i].next)
        if(!vis[y]&&y!=f[x])
            f[q[++tail]=y]=x;
    }

    for(i=2;i<=mx;++i)cnt[i]+=cnt[i-1];
    while(x=q[--head])
    {
        if((sz[x]<<1)>=tail)break;
        sz[f[x]]+=sz[x];
    }
    rt=x;
    t_f[rt]=fr;deep[rt]=dep;
    vis[rt]=1;

    now_b=b[dep];
    f[q[tail=1]=rt]=0;
    us u=(cnt[mx]>>5)+1; U[rt]=u;
    for(head=1;head<=tail;++head)
    {
        x=q[head];a[x]=cnt[a[x]]; 
        now_b[x]=new ui [u];
        if(head>1) for(i=0;i<u;++i)now_b[x][i]=now_b[f[x]][i];
        else for(i=0;i<u;++i)now_b[x][i]=0;
        now_b[x][a[x]>>5]|=1<<(a[x]&31);
        for(i=t[x];y=l[i].to;i=l[i].next)
        if(!vis[y]&&y!=f[x])
        {
            f[y]=x;q[++tail]=y;
        }
    }
    ++dep;
    for(int i=t[rt];y=l[i].to;i=l[i].next)
    if(!vis[y]) build(y,dep,rt);
}

us get_lca(us x,us y)
{
    while(x!=y)
    if(deep[x]>deep[y])x=t_f[x];
    else y=t_f[y];
    return x;
}

namespace kcz
{
    const int U=1<<16;
    us f[U+1];
    void init()
    {
        for(i=1;i<=U;++i)f[i]=f[i-(i&-i)]+1; 
    }
    us count(ui x)
    {
        return f[x&(U-1)]+f[x>>16];
    }
};

const int ch_top=5000000;
char ch[ch_top],*now_r=ch;
void read(int &x)
{
    while(*now_r<'-')++now_r;
    if(*now_r=='-')
    {
      for(x=*++now_r-'0';*++now_r>='0';) x=(x<<1)+(x<<3)+*now_r-'0';
      x=-x;
    }
    else
    {
        for(x=*now_r-'0';*++now_r>='0';) x=(x<<1)+(x<<3)+*now_r-'0';
    }
}

us ans;

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    int q;
    fread(ch,1,ch_top,stdin);
    read(n);read(q);
    for(i=1;i<=n;++i)read(a[i]);
    lisan();
    for(i=1;i<n;++i)
    {
        read(x);read(y);
        l[++e]=(edge){y,t[x]};t[x]=e;
        l[++e]=(edge){x,t[y]};t[y]=e;
    }
    build(1,0,0);
    kcz::init();
    while(q--)
    {
        read(x);read(y);//x=x^ans; 
        us lca=get_lca(x,y);
        X=b[deep[lca]][x];Y=b[deep[lca]][y];
        ans=0;
        for(i=0;i<U[lca];++i) ans+=kcz::count(X[i]|Y[i]);
        printf("%d\n",ans);
    }
}