本文会摘取一部分丙上~甲下的题面（上位绿~下位黑）

初探

数据结构是竞赛中最重要的部分。

从最开始的数组出发，根据指针的不同可以形成不同的处理方式：

Cowreography G

本题一定是有一个解决规律的，具体来说1往后换了之后再往前换是不优的。

接下来提出确定对于一个1换到的位置的算法，

具体说，两个数交换的代价是 (X-Y)/K 上取整，所以有一种想法就是尽量让整除的互换，不过这个操作会造成一些额外代价，不出意料得用数据结构维护。

总结一下，只要可以匹配就得优先匹配，而优先匹配的还得是余数相近的（<=），不然就是最小的。

以上性质都是可以手画出来的。

难度评分：乙下。

丹钓战

区间查，无修改。

从b维度来看就是需要单调上升，有可能是单调栈算法。

注意一下，可以算一个数到哪一个进入时会弹出。

然后询问需要判断到底到那个数时所有都会被弹出去。

因为是所有都被弹出去，等价于第一个数什么时候被弹出去。

单调栈+倍增解决即可。

难度评分：丙上

树型结构

树型结构是数据结构中很重要的一部分。主要包括线段树和平衡树。

天天爱打卡

线段树优化DP，

首先O(nm)做法是容易得到的，考虑对此的优化。

一个想法是将所有的贡献提前计算，

这样需要支持区间加，前缀清除，前缀求最大值。

然后我们发现只有部分区间需要修改，所以可以打包处理离散化。

难度评分乙下

列队

动态开点线段树，

我们可以通过打标记跳过出队人数，对于每一行都需要进行维护，但是有个例外：最后一列因为需要加入所有出队人数会比较特殊。

找到要处理的人所在的行数后，如果是<=m不用再处理，如果不是，则会是出队过的数，而这个数可以用另一个方法找到。

举个例子，如果是要找x行最后一个数，输出后，再继续找最后一个数，只需要对列线段树（n+q）打标记再遗传即可。

如果是数组中间的数，因为是新数，可以概括为找到后打标记，找到的数>=m时，注意=算上是为了便于打包处理（对最后一列的数），那就一定是从最右列从这个位置到下的第ans-m+1个。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,m,q,rt[N],tot;
struct TR{int lc,rc,sum;}tr[N<<4];
long long num[N*2],ans;vector<long long>g[N];
inline int ask(int &x,int l,int r,int k){   // 修改查询一起
    if(!x) x=++tot,tr[x].sum=r-l+1;
    tr[x].sum--;
    if(l==r) return l;
    int mid=l+r>>1,res=tr[x].lc?tr[tr[x].lc].sum:mid-l+1;
    return k<=res?ask(tr[x].lc,l,mid,k):ask(tr[x].rc,mid+1,r,k-res);
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)num[i]=(long long)i*m;
    for(int i=1,x,y;i<=q;i++){
        scanf("%d%d",&x,&y);
        if(y==m) num[n+i]=num[ask(rt[0],1,n+q,x)];
        else{
            ans=ask(rt[0],1,n+q,x);
            g[x].push_back(num[ans]);
            ans=ask(rt[x],1,m+q,y);
            num[n+i]=ans>=m?g[x][ans-m]:ans+m*(x-1ll);
        }printf("%lld\n",num[n+i]);
    }
}

难度评分乙中

数据传输

如果将某点或某点儿子作为状态，状态数太多，但是观察后发现只要将到某点的距离看作状态即可。

用矩阵形式转移，LCA接路径即可，注意特判接头处的特殊情况。

难度评分乙中

比赛

用单调栈转化后变为区间xy和问题加维护区间覆盖。

用矩阵表示，然后转移一些标记就可以了。

难度评分甲下

Xor-Forces

先转化，区间颜色段个数等于区间长度减去相邻同色对数

难点是线段树的下标为异或，需要发现一些性质再做：观察到这个的本质是交换线段树的左右结点。

因为结点顺序可能会变化，但是不同的情况只有区间顺序种，

所以用线段树维护vector就可以传递懒标记了。

难度评分：乙中