题意：定义一个偶串为一个可写为一个字符串复制两次的字符串。S为一个偶串，定义f(S)为在S后加最少的字符（大于等于1个）使S成为的偶串。

设f(SS)=STST，g(S)=ST。则T为S最小的周期。
$$g(ST)=STT(|T| \\mid |S|) $$
$$g(ST)=STS(|T| \\nmid |S|)$$

#include <bits/stdc++.h>
using namespace std;
const int N=210000;
#define ll long long
char s[N];
ll L,R;
int nex[N];
ll len[210];
struct node
{
    ll a[26];
    void init(int x)
    {
        for(int i=1;i<=x;i++)
            a[s[i]-'a']++;
    }
    friend node operator + (const node &r1,const node &r2)
    {
        node ret;
        for(int i=0;i<26;i++)
            ret.a[i]=r1.a[i]+r2.a[i];
        return ret;
    }
    friend node operator - (const node &r1,const node &r2)
    {
        node ret;
        for(int i=0;i<26;i++)
            ret.a[i]=r1.a[i]-r2.a[i];
        return ret;
    }
    void print()
    {
        for(int i=0;i<26;i++)
            printf("%lld ",a[i]);
        puts("");
    }
}v[210];
node calc(ll x)
{
    int p;
    for(p=1;;p++)
        if(len[p]>=x)break;
    node ret,t;
    memset(&ret,0,sizeof(ret));
    memset(&t,0,sizeof(t));
    for(;p>=1;p--)
        if(len[p]<=x)
        {
            ret=ret+v[p];
            x-=len[p];
        }
    t.init(x);
    ret=ret+t;
    return ret;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%s%lld%lld",s+1,&L,&R);
    len[2]=strlen(s+1)/2;
    nex[1]=0;
    for(int i=2,j=0;i<=len[2];i++)
    {
        while(j&&s[j+1]!=s[i])
            j=nex[j];
        if(s[j+1]==s[i])j++;
        nex[i]=j;
    }
    len[1]=len[2]-nex[len[2]];
    v[1].init(len[1]);
    v[2].init(len[2]);
    for(int i=3;;i++)
    {
        len[i]=len[i-1]+len[i-2];
        v[i]=v[i-1]+v[i-2];
        if(len[i]>=R)break;
    }
    (calc(R)-calc(L-1)).print();
    return 0;
}

整体二分裸题

#include <bits/stdc++.h>
using namespace std;
#define N 110000
#define PA pair<int,int>
int n,m,Q;
int X[N],Y[N],ans[N];
struct node
{
    int x,y,tar,pos;
}a[N],b[N];
struct Ufs
{
    int now;
    int fa[N],size[N],mem[N];
    void init()
    {
        for(int i=1;i<=n;i++)
            fa[i]=i,size[i]=1;
    }
    int find(int x){return fa[x]==x ? x : find(fa[x]);}
    void move(int tar)
    {
        int x,y;
        while(now<tar)
        {
            now++;
            if((x=find(X[now]))==(y=find(Y[now])))
                mem[now]=0;
            else
            {
                if(size[y]>size[x])swap(x,y);
                size[x]+=size[y];
                fa[y]=x;
                mem[now]=y;
            }
        }
        while(now>tar)
        {
            if(x=mem[now])
            {
                size[fa[x]]-=size[x];
                fa[x]=x;
            }
            now--;
        }
    }
    int calc(int x,int y)
    {
        x=find(x);y=find(y);
        if(x==y)return size[x];
        return size[x]+size[y];
    }
}ufs;
void solve(int l1,int r1,int l2,int r2)
{
    if(l2>r2)return;
    if(l1==r1)
    {
        for(int i=l2;i<=r2;i++)
            ans[a[i].pos]=l1;
        return;
    }
    int mid=(l1+r1)>>1,lm=l2,rm=r2;
    ufs.move(mid);
    for(int i=l2;i<=r2;i++)
    {
        if(ufs.calc(a[i].x,a[i].y)>=a[i].tar)
            b[lm++]=a[i];
        else b[rm--]=a[i];
    }
    for(int i=l2;i<=r2;i++)a[i]=b[i];
    solve(l1,mid,l2,lm-1);
    solve(mid+1,r1,rm+1,r2);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&X[i],&Y[i]);
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].tar);
        a[i].pos=i;
    }
    ufs.init();
    solve(1,m,1,Q);
    for(int i=1;i<=Q;i++)
        printf("%d\n",ans[i]);
    return 0;
}

题意：m个区间，对1到n的i分别求有多少个区间中出现了i的倍数。

对于数i，长度大于等于的区间i一定包含i的倍数，长度小于i的区间最多包含一个i的倍数，从小到大枚举i，每次把长度小于i的区间从答案中减掉，插入树状数组中。枚举i的倍数，对于i的每个倍数在树状数组中查询。
写了个sb线段树。。。

#include <bits/stdc++.h>
using namespace std;
#define ls l,mid,now<<1
#define rs mid+1,r,now<<1|1
const int N=310000,M=110000;
int n,m,cnt;
struct node
{
    int l,r;
    friend bool operator < (const node &r1,const node &r2)
    {return r1.r<r2.r;}
}a[N];
vector<int>vec[M];
int b[M*20],pos[M],ed[M],beg[M],nv[M*20];
int val[M*20],bj[M*80],ans[M];
void pushdown(int now)
{
    bj[now<<1]+=bj[now];
    bj[now<<1|1]+=bj[now];
    bj[now]=0;
}
void modify(int l,int r,int now,int pos,int v)
{
    if(l==r)
    {
        val[l]+=bj[now]*nv[l];
        bj[now]=0;nv[l]=v;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(now);
    if(mid>=pos)modify(ls,pos,v);
    else modify(rs,pos,v);
}
void insert(int l,int r,int now,int lq,int rq)
{
    if(lq<=l&&r<=rq)
        {bj[now]++;return;}
    int mid=(l+r)>>1;
    if(mid>=lq)insert(ls,lq,rq);
    if(mid<rq) insert(rs,lq,rq);
}
void down(int l,int r,int now)
{
    if(l==r)
    {
        val[l]+=bj[now]*nv[l];
        return;
    }
    int mid=(l+r)>>1;
    pushdown(now);
    down(ls);down(rs);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].l,&a[i].r);
    sort(a+1,a+1+n);
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j+=i)
            vec[j].push_back(i);
    for(int i=1;i<=m;i++)
    {
        beg[i]=cnt+1;
        for(int j=0;j<vec[i].size();j++)
            b[++cnt]=vec[i][j];
        ed[i]=cnt;
    }
    for(int i=1,now=1,t=0;i<=m;i++)
    {
        while(t<ed[i])
        {
            t++;
            if(pos[b[t]])
                modify(1,cnt,1,pos[b[t]],0);
            modify(1,cnt,1,t,1);
            pos[b[t]]=t;
        }
        while(now<=n&&a[now].r==i)
        {
            insert(1,cnt,1,beg[a[now].l],ed[a[now].r]);
            now++;  
        }
    }
    down(1,cnt,1);
    for(int i=1;i<=cnt;i++)
        ans[b[i]]+=val[i];
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

题意：给出一棵树，树上有一些关键点，一个点集可行当且仅当它可以表示为一个关键点与距它距离d以内的所有点的集合。求可行点集总数。

先不考虑关键点（设所有点均为关键点）
对于一个除全集以外的可行点集可以表示它的点组成树的一个子树。只在子树中d最小的点处统计这个点集。可以发现子树中这样的点只有一个。
因此计算一个点的贡献时，设以他为根时深度最大的子树距该点距离为f1，深度次大的子树距该点距离为f2。则该点的d取值范围为[0,min(f1-1,f2+1)]
当存在关键点时，选取的d必须使一个关键点包含在可行子树中，因此选取的d必须完整覆盖一个包含关键点的子树

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=210000;
int n,tot;
char s[N];
int head[N],nex[N<<1],to[N<<1];
int f1[N],f2[N],g[N],lb[N],size[N];
ll ans;
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void upd(int &x,int &y,int z)
{
    if(z>x)y=x,x=z;
    else if(z>y)y=z;
}
void dfs1(int x,int y)
{
    size[x]=s[x]-'0';
    for(int i=head[x],t;i;i=nex[i])if((t=to[i])!=y)
    {
        dfs1(t,x);
        size[x]+=size[t];
        upd(f1[x],f2[x],f1[t]+1);
        if(size[t])
            lb[x]=min(lb[x],f1[t]+1);
    }
}
void dfs2(int x,int y)
{
    for(int i=head[x],t,d;i;i=nex[i])if((t=to[i])!=y)
    {
        g[t]=max(g[x],f1[t]+1==f1[x] ? f2[x] : f1[x])+1;
        if(size[t]!=size[1])
            lb[t]=min(lb[t],g[t]);
        dfs2(t,x);
    }
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
        if(s[i]=='0')lb[i]=n+1;
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++)
    {
        upd(f1[i],f2[i],g[i]);
        ans+=max(0,min(f1[i]-1,f2[i]+1)-lb[i]+1);
    }
    printf("%lld\n",ans+1);
    return 0;
}

题意：给出一个数列a，一个数的初始值为D，按数列顺序操作，每次把D变为$$min(D,abs(D-a[i]))$$。q个询问，每次询问任意修改a数列一个位置数后能否使操作a序列后D值不为0。

设$$b[i]$$表示最小的D初始值使经过i及以后的操作后值不为0。
则$$b[n+1]=1$$
如果$$\lfloor\frac{a[i]}{2}\rfloor\ge b[i+1]$$则$$b[i]=b[i+1]$$,因为$$a[i]$$操作无效
否则$$b[i]=b[i+1]+a[i]$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=510000;
int n,q;
int a[N],d[N];
ll b[N];
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&d[0]);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    b[n+1]=1;
    for(int i=n;i>=1;i--)
    {
        if(a[i]/2>=b[i+1])b[i]=b[i+1];
        else b[i]=b[i+1]+a[i];
    }
    for(int i=1;i<=n;i++)
        d[i]=min(d[i-1],abs(d[i-1]-a[i]));
    scanf("%d",&q);
    for(int i=1,t;i<=q;i++)
    {
        scanf("%d",&t);
        puts(b[t+1]<=d[t-1] ? "YES" : "NO");
    }
    return 0;
}