链接

A

理解一下题意，然后玩几组样例就能发现，实际上就是\(k\)个\(i\)等价于\(1\)个\(i-1\)。所以就类似于\(k\)进制进行进位，如果最后\(0\)位上不是\(0\)，那么就存在划分方案。否则就不存在划分方案。

输出第一次划分方案就记录一下每个数字是不是后面的数字凑出来的。如果是的话就像后面数字连边。这样就形成了一棵\(k\)叉树。最后\(dfs\)一遍输出即可。

考场上\(vector\)下标从1开始记录了。就\(wa\)惨了。。。

/*
* @Author: wxyww
* @Date: 2019-08-04 11:41:21
* @Last Modified time: 2019-08-04 16:08:45
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 200000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int vis[N],tot;
int n,K;
vector<int>e[N * 10],ans[N];
void print(int pos,int u) {
    if(u <= n) {
        ans[pos].push_back(u);vis[u] = 1;return;
    }
    int k = e[u].size();
    for(int i = 0;i < k;++i) {
        print(pos,e[u][i]);
    }
}
int main() {
    int T = read();
    while(T--) {

         n = read(),K = read();
        tot = n;        
        for(int i = 1;i <= n;++i) e[read()].push_back(i);

        for(int i = n;i > 1;--i) {
            int k = e[i].size();
            while(k >= K) {
                ++tot;
                for(int j = 1;j <= K;++j,k--) {
                    e[tot].push_back(e[i][k - 1]);
                }
                e[i - 1].push_back(tot);
            }
        }
        if(e[1].size() < K) {
            puts("0");
            for(int i = 0;i <= tot;++i) e[i].clear();
            for(int i = 0;i <= K;++i) ans[i].clear();
            memset(vis,0,sizeof(vis)); 
            continue;
        }
        puts("1");


        for(int i = 0;i < K;++i) {
            int k = e[1][i];
            print(i + 1,k);
        }

        for(int i = 1;i <= n;++i) if(!vis[i]) ans[1].push_back(i);
        
        for(int i = 1;i <= K;++i) {
            int k = ans[i].size();
            printf("%d ",k);
            for(int j = 0;j < k;++j) printf("%d ",ans[i][j]);
            puts("");
        }
    
        for(int i = 0;i <= tot;++i) e[i].clear();
        for(int i = 0;i <= K;++i) ans[i].clear();
        memset(vis,0,sizeof(vis)); 

    }

    return 0;
}

B

考场上只会一个暴力并查集的做法。就是每次暴力将相同的位置并起来，最后查询。然鹅，，，，没注意到"后面一个区间不能相交"这个重要条件。。。然后就硬生生把复杂度对的42分程序通过数据分治改成了22分的好成绩233.。。

只要将并查集改成暴力这题就能A了。。。
对于已经给出的每一位，都根据给出的相等条件不断向前跳，将这个字符储存在第一个可知的位置。对于后面的询问，用同样的方法向前跳即可。

考虑一下向前跳的复杂度。

如图，我们已知两个黑色矩形区域是相等的。那么显然这两个区域都含有一个长度为t的循环节。我们如果暴力跳的话就要跳\(\frac{len}{t}\)次。所以我们直接计算出最前面那个循环节中与当前查询字符相等的位置，直接跳过去即可。
这样每个条件都只会最多跳一次。所以复杂度就是\(O(m)\)的。

/*
* @Author: wxyww
* @Date: 2019-08-04 19:52:20
* @Last Modified time: 2019-08-04 20:16:31
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N = 1000100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m1,m2,Q;
struct node {
    int l1,r1,l2,r2;
}a[N];
pair<int,char> b[N];
bool cmp(const node &A,const node &B) {
    return A.l2 < B.l2;
}
map<int,char>ans;

int erfen(int x) {
    int ret = 0,l = 1,r = m2;
    while(l <