CCPC#2020威海

G.Caesar Cipher

很经典的hash+线段树，以后遇到“求解序列是否相同”都可以试试hash

这里的数字要对65536取模，可以存储每个区间的mn和mx值，这样就可以知道是否有数字达到了65536，然后，对于任何满足内部所有数字都达到了65536的区间清零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5e5+5;
const ll mod1=998244353;
const ll mod2=1e9+7;
const int up=65536;
int n,q;
int a[maxn];
ll p1[maxn],pre[maxn];
struct Tree{
    ll hsh;
    int mx;
    int mn;
    int tag;
    int rem;
}t[maxn<<2];
void push_up(int rt){
    t[rt].hsh=t[rt<<1].hsh+t[rt<<1|1].hsh,t[rt].hsh%=mod2;
    t[rt].mx=max(t[rt<<1].mx,t[rt<<1|1].mx);
    t[rt].mn=min(t[rt<<1].mn,t[rt<<1|1].mn);
}
void push_dn(int rt,int l,int r){
    int mid=l+r>>1;
    if(t[rt].rem){
        t[rt<<1].mx=t[rt<<1|1].mx=0;
        t[rt<<1].mn=t[rt<<1|1].mn=0;
        t[rt<<1].hsh=t[rt<<1|1].hsh=0;
        t[rt<<1].rem=t[rt<<1|1].rem=1;
        t[rt<<1].tag=t[rt<<1|1].tag=0;
        t[rt].rem=0;
    }
    t[rt<<1].tag+=t[rt].tag,t[rt<<1|1].tag+=t[rt].tag;
    t[rt<<1].mn+=t[rt].tag,t[rt<<1|1].mn+=t[rt].tag;
    t[rt<<1].mx+=t[rt].tag,t[rt<<1|1].mx+=t[rt].tag;
    t[rt<<1].hsh+=((pre[mid]-pre[l-1])+mod2)%mod2*t[rt].tag%mod2,t[rt<<1].hsh%=mod2;
    t[rt<<1|1].hsh+=((pre[r]-pre[mid])+mod2)%mod2*t[rt].tag%mod2,t[rt<<1|1].hsh%=mod2;
    t[rt].tag=0;
}
void build(int rt,int l,int r){
    int mid=l+r>>1;
    if(l==r){
        t[rt].mx=a[l];
        t[rt].mn=a[l];
        t[rt].tag=0;
        t[rt].hsh=a[l]*p1[l],t[rt].hsh%=mod2;
        return ;
    }
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    push_up(rt);
}
void update(int rt,int l,int r,int xl,int xr){
    int mid=l+r>>1;
    if(xl==l&&r==xr){
        t[rt].mn++;
        t[rt].tag++;
        t[rt].mx++;
        t[rt].hsh+=pre[r]-pre[l-1];
        t[rt].hsh=(t[rt].hsh+mod2)%mod2;
        return;
    }
    push_dn(rt,l,r);
    if(xl<=mid)update(rt<<1,l,mid,xl,min(xr,mid));
    if(xr>mid)update(rt<<1|1,mid+1,r,max(xl,mid+1),xr);
    push_up(rt);
}
void modify(int rt,int l,int r){
    int mid=l+r>>1;
    if(t[rt].mn==up){
        t[rt].mn=t[rt].mx=0;
        t[rt].tag=0;
        t[rt].hsh=0;
        t[rt].rem=1;
        return ;
    }
    push_dn(rt,l,r);
    if(t[rt<<1].mx==up)modify(rt<<1,l,mid);
    if(t[rt<<1|1].mx==up)modify(rt<<1|1,mid+1,r);
    push_up(rt);
}
ll get_hsh(int rt,int l,int r,int xl,int xr){
    int mid=l+r>>1;
    if(xl==l&&xr==r){
        return t[rt].hsh;
    }
    push_dn(rt,l,r);
    ll res=0;
    if(xl<=mid)res+=get_hsh(rt<<1,l,mid,xl,min(xr,mid));
    if(xr>mid)res+=get_hsh(rt<<1|1,mid+1,r,max(xl,mid+1),xr);
    return res%mod2;
}
int main(){
  //  freopen("input.txt","r",stdin);
  //  freopen("output.txt","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    p1[0]=pre[0]=1;
    for(int i=1;i<=n;i++){
        p1[i]=p1[i-1]*mod1;
        p1[i]%=mod2;
        pre[i]=pre[i-1]+p1[i];
        pre[i]%=mod2;
    }
    build(1,1,n);
    while(q--){
        int opt;
        scanf("%d",&opt);
        if(opt==1){
            int l,r;
            scanf("%d%d",&l,&r);
            update(1,1,n,l,r);
            if(t[1].mx==up){
                modify(1,1,n);
            }
        }
        else {
            int x,y,len;
            scanf("%d%d%d",&x,&y,&len);
            if(x>y)swap(x,y);
           // printf("$$%d %d ##%lld %lld\n",x,y,get_hsh(1,1,n,x,x+len-1)*p1[y-x]%mod2,get_hsh(1,1,n,y,y+len-1));
            if(get_hsh(1,1,n,x,x+len-1)*p1[y-x]%mod2==get_hsh(1,1,n,y,y+len-1))puts("yes");
            else puts("no");
        }
    }
    return 0;
}

I.Sean the Cuber

神仙题目，就算看了题解也不知道从何下手…（如果要我自己写可能要写个2天吧T_T）

于是果断看别人的AC代码，在这里贴一下Jiangly的代码（膜拜jls.jpg）

这个题的主要难在实现，所以题解主要看我下面的代码注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>

std::map<std::string, int> corner{
    {"BRY", 0},
    {"YRG", 1},
    {"GRW", 2},
    {"WRB", 3},
    {"BOW", 4},
    {"WOG", 5},
    {"GOY", 6},
    {"YOB", 7}
};

using Perm = std::array<int, 24>;

const Perm rot{2, 0, 1, 10, 11, 9, 14, 12, 13, 22, 23, 21, 20, 18, 19, 16, 17, 15, 8, 6, 7, 4, 5, 3};

Perm twist[6]{
    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 15, 16, 17, 18, 19, 20, 21, 22, 23, 12, 13, 14},
    {0, 1, 2, 3, 4, 5, 10, 11, 9, 14, 12, 13, 16, 17, 15, 8, 6, 7, 18, 19, 20, 21, 22, 23},
    {0, 1, 2, 7, 8, 6, 17, 15, 16, 9, 10, 11, 12, 13, 14, 19, 20, 18, 5, 3, 4, 21, 22, 23}
};

Perm mul(const Perm &a, const Perm &b) {
    Perm c;
    for (int i = 0; i < 24; ++i) c[i] = a[b[i]];
    return c;
}

Perm inv(const Perm &a) {
    Perm b;
    for (int i = 0; i < 24; ++i) b[a[i]] = i;
    return b;
}

Perm get(char s[24]) {
    Perm a;
    for (int i = 0; i < 24; i += 3) {
        for (int j = 0; j < 3; ++j) {
            auto t = std::string({s[i + j], s[i + (j + 1) % 3], s[i + (j + 2) % 3]});
            if (corner.count(t)) {//确定每个面的实际编号
                int v = corner[t];
                a[i + j] = 3 * v;
                a[i + (j + 1) % 3] = 3 * v + 1;
                a[i + (j + 2) % 3] = 3 * v + 2;
            }
        }
    }
    
    int k = (std::find(a.begin(), a.end(), 0) - a.begin()) / 3;
    if (k >= 4) {//把第一个块转到右侧
        for (int i = 0; i < 12; ++i) std::swap(a[i], a[i + 12]);
        k -= 4;
    }
    
    Perm temp;//把第一个块转到右侧第一个
    for (int i = 0; i < 12; ++i) temp[i] = a[(i + 3 * k) % 12];
    for (int i = 0; i < 12; ++i) temp[12 + (i + 3 * k) % 12] = a[12 + i];
    a = std::move(temp);
    
    while (a[0] != 0) a = mul(a, rot);//把第一个块的方向置为初始方向
    
    return a;
}

int fac[7];

int hash(const Perm &a) {
    int res = 0;
    int x = (1 << 7) - 1;
    for (int i = 0; i < 7; ++i) {//因为第一个块的位置已经定了，所以现在只需要确定其他块的位置
        int v = a[3 * i + 3] / 3 - 1;
        res += fac[6 - i] * __builtin_popcount(x & ((1 << v) - 1));
        x ^= 1 << v;
    }
    for (int i = 1; i < 7; ++i) {//确定位置之后，再确定6个角块的方向
        int v = a[3 * i] % 3;
        res = 3 * res + v;
    }
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    fac[0] = 1;
    for (int i = 1; i < 7; ++i) fac[i] = i * fac[i - 1];
    
    for (int i = 0; i < 3; ++i) twist[i + 3] = inv(twist[i]);//顺时针拧上面一层，等价于逆时针拧下面一层

    constexpr int N = 3674160;
    int dis[N];
    std::fill(dis, dis + N, -1);
    
    Perm a;
    std::iota(a.begin(), a.end(), 0);
    dis[hash(a)] = 0;
    std::queue<Perm> que;
    que.push(a);
    
    while (!que.empty()) {
        auto u = que.front();
        que.pop();
        
        int d = dis[hash(u)];
        
        for (int i = 0; i < 6; ++i) {
            auto v = mul(u, twist[i]);
            int h = hash(v);
            if (dis[h] == -1) {
                dis[h] = d + 1;
                que.push(v);
            }
        }
    }
    
    int t;
    std::cin >> t;
    
    while (t--) {//注意这里每个角块的三个面的下标都是相邻的，为[3*(i-1),3*i)
        char a[24], b[24], foo;
        std::cin >> a[20] >> a[3] >> foo >> b[20] >> b[3];
        std::cin >> a[21] >> a[2] >> foo >> b[21] >> b[2];
        std::cin >> a[19] >> a[22] >> a[23] >> a[0] >> a[1] >> a[4] >> a[5] >> a[18] >> foo >> b[19] >> b[22] >> b[23] >> b[0] >> b[1] >> b[4] >> b[5] >> b[18];
        std::cin >> a[16] >> a[13] >> a[12] >> a[11] >> a[10] >> a[7] >> a[6] >> a[17] >> foo >> b[16] >> b[13] >> b[12] >> b[11] >> b[10] >> b[7] >> b[6] >> b[17];
        std::cin >> a[14] >> a[9] >> foo >> b[14] >> b[9];
        std::cin >> a[15] >> a[8] >> foo >> b[15] >> b[8];
        
        auto u = get(a), v = get(b);
        
        v = mul(inv(u), v);
        std::cout << dis[hash(v)] << "\n";
    }
    
    return 0;
}