2024.10.10

First Post:

Last Update:

Word Count:
4.4k

Read Time:
22 min

代码能力怎么这么弱？代码能力怎么这么弱？代码能力怎么这么弱？

昨天调题调破防了，忘了写。今天补上。

【模板】回滚莫队&不删除莫队

增加是好维护的，删除是不好维护的，考虑回滚莫队。

可以用栈维护一下，然后栈序撤销。

但是写挂了，不想调，所以没有代码。

upd：唐。

今天把代码补了，发现自己以前唐完了。

以前我对每个颜色只记录了最左侧的位置，然后一直错。

事实上应该记录最左侧和最右侧的位置。

不知道自己怎么做到这么唐的。

代码事实上很好写。

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
#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=2e5+10,maxm=500;
int n,m,siz,tot;
int a[maxn],b[maxn],ans[maxn];
int st[maxm],ed[maxm],bel[maxn];
int buc[maxn],buc1[maxn],tong[maxn];
stack<pair<int,pii>> stk;
struct query{
    int l,r,id;
    inline bool operator < (const query &a)const{
        if(bel[l]==bel[a.l]) return r<a.r;
        return bel[l]<bel[a.l];
    }
}q[maxn];
inline void init(){
    siz=sqrt(n);
    tot=n/siz;
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<n) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=n;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i;
}
inline void solve(int l,int r,int id){
    int res=0;
    for(re int i=l;i<=r;++i){
        if(!tong[a[i]]) tong[a[i]]=i;
        else res=max(res,i-tong[a[i]]);
    }
    for(re int i=l;i<=r;++i) tong[a[i]]=0;
    ans[id]=res;
}
inline void add(int x,int &res,bool type){
    if(type) stk.push({x,{buc[a[x]],buc1[a[x]]}});
    if(!buc[a[x]]) buc[a[x]]=x;
    else buc[a[x]]=min(buc[a[x]],x);
    if(!buc1[a[x]]) buc1[a[x]]=x;
    else buc1[a[x]]=max(buc1[a[x]],x);
    res=max(res,buc1[a[x]]-buc[a[x]]);
}
inline void undo(){
    pair<int,pii> tmp=stk.top();stk.pop();
    buc[a[tmp.fi]]=tmp.se.fi;
    buc1[a[tmp.fi]]=tmp.se.se;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    int len=unique(b+1,b+n+1)-(b+1);
    for(re int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
    cin>>m;
    for(re int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    init();
    sort(q+1,q+m+1);
    int l=1,r=0,lst=0,mx=0;
    for(re int i=1;i<=m;++i){
        if(bel[q[i].l]==bel[q[i].r]) solve(q[i].l,q[i].r,q[i].id);
        else{
            if(lst^bel[q[i].l]){
                memset(buc,0,sizeof buc);
                memset(buc1,0,sizeof buc1);
                l=ed[bel[q[i].l]]+1,r=ed[bel[q[i].l]];
                mx=0,lst=bel[q[i].l];
            }
            while(r<q[i].r) add(++r,mx,0);
            int tmp=mx,l1=l;
            while(l1>q[i].l) add(--l1,tmp,1);
            while(l1<l) ++l1,undo();
            ans[q[i].id]=tmp;
        }
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}

曼哈顿交易

首先，你要先读对题。

题目让求的是出现次数的第k小，不是第k小的出现次数。

且这个第k小是不去重的。

因为读错题又挂了半天，呃呃。

区间查询，容易想到莫队。

值域上的第k小且要平衡复杂度，容易想到值域分块。

莫队加值域分块即可。

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
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e5+10,maxm=350;
int n,m,siz,tot;
int a[maxn],b[maxn],ans[maxn];
int st[maxm],ed[maxm],bel[maxn];
int cnt1[maxn],cnt2[maxn],cnt3[maxm];
struct query{
    int l,r,k,id;
}q[maxn];
inline bool cmp(query a,query b){return ((a.l/siz)^(b.l/siz))?(a.l/siz)<(b.l/siz):((a.l/siz)&1)?a.r<b.r:a.r>b.r;}
inline void init(){
    siz=sqrt(n);
    tot=n/siz;
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<n) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=n;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i;
}
inline void add(int x){
    --cnt2[cnt1[x]];
    --cnt3[bel[cnt1[x]]];
    ++cnt1[x];
    ++cnt2[cnt1[x]];
    ++cnt3[bel[cnt1[x]]];
}
inline void del(int x){
    --cnt2[cnt1[x]];
    --cnt3[bel[cnt1[x]]];
    --cnt1[x];
    ++cnt2[cnt1[x]];
    ++cnt3[bel[cnt1[x]]];
}
inline int query(int k){
    int id=0;
    for(re int i=1;i<=tot;++i){
        if(k-cnt3[i]<=0){id=i;break;}
        k-=cnt3[i];
    }
    if(!id) return -1;
    for(re int i=st[id];i<=ed[id];++i){
        if(k-cnt2[i]<=0) return i;
        k-=cnt2[i];
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    int len=unique(b+1,b+n+1)-(b+1);
    for(re int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
    for(re int i=1;i<=m;++i) cin>>q[i].l>>q[i].r>>q[i].k,q[i].id=i;
    init();
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(re int i=1;i<=m;++i){
        while(r<q[i].r) add(a[++r]);
        while(l>q[i].l) add(a[--l]);
        while(r>q[i].r) del(a[r--]);
        while(l<q[i].l) del(a[l++]);
        ans[q[i].id]=query(q[i].k);
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}

美好的每一天

因为是重排以后的回文串，所以这个限制本质上就是对每种字符的出现次数的奇偶性的限制。

因为我们只关心奇偶性，所以想到异或。

因为字符集很小，所以考虑状压。

我们用一个 26 位的数表示每种字符的出现次数的奇偶性。

那么对于一个区间，我们可以先把前缀异或求出来，然后就很好得到区间异或值了。

设 为前缀异或，询问区间为 ，那么询问就被转化成了：在 种选取两个不同位置 ，使得 等于 0 或 2 的若干次方（0 代表每种字符都出现偶数次，2 的若干次方代表只有一种字符出现奇数次）。

指针移动时的修改就对每种字符都算一下就行。

和[CQOI2018] 异或序列很像。

事实上可以二离做到更优复杂度，但是没必要，字符集太小了。

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
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=6e4+10,maxv=(1<<26)+10;
int n,m,siz,now;
int a[maxn],ans[maxn];
int buc[maxv];
struct query{
    int l,r,id;
}q[maxn];
inline bool cmp(query a,query b){return ((a.l/siz)^(b.l/siz))?(a.l/siz)<(b.l/siz):((a.l/siz)&1)?a.r<b.r:a.r>b.r;}
inline void add(int x){
    now+=buc[x];
    ++buc[x];
    for(re int i=0;i<26;++i) now+=buc[x^(1<<i)];
}
inline void del(int x){
    --buc[x];
    now-=buc[x];
    for(re int i=0;i<26;++i) now-=buc[x^(1<<i)];
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i){
        char c;
        cin>>c;
        a[i]=1<<(c-'a');
        a[i]^=a[i-1];
    }
    for(re int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,--q[i].l,q[i].id=i;
    siz=sqrt(n);
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(re int i=1;i<=m;++i){
        while(r<q[i].r) add(a[++r]);
        while(l>q[i].l) add(a[--l]);
        while(r>q[i].r) del(a[r--]);
        while(l<q[i].l) del(a[l++]);
        ans[q[i].id]=now;
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}

「TERRA-OI R1」神，不惧死亡

首先得先把这个游戏想明白。

事实上是个简单贪心。

不难发现，从小往大消除就是最优的。

然后手玩样例可以发现，最后得到的最优结果就是最小的出现次数为偶数的数的后继。

不难理解，因为你可以先把小于这个数的数全消成只剩 1 个，然后把这个数消没，最后得到的就是这个数的后继。

而且这一定是最优的。

假设它的后继不是最优，那么我们最后能得到一个比它的后继大的数，那么这就要求这个数的后继和这个数最后必须被消没。

但因为这个数出现次数为偶数，所以它不能被大数消除的亡语给带没。所以如果我们要把它的后继给消没，那么此时的结果就是这个数。这是不优的。

如果我们先把这个数消没，那么得到的一定是后继。

命题得证。

那么现在问题变成了：单点修改，区间查询值域在一段区间上的数里，最小的出现次数为偶数的数的后继。

先不考虑修改，容易想到莫队。

那么需要维护值域上的信息，容易想到值域分块。

因为要带修，所以带修莫队+值域分块即可。

值域分块维护每个数的出现次数，每个块内出现次数为偶数的数的个数，每个块的数的个数（去重或不去重都行，没必要去重，但我写的去重）。

查询时，我写成了查两次：先找出来最小的出现次数为偶数的数，然后找这个数的后继。

感觉比较好理解。

但我很唐，所以写出来了一堆唐氏错误：

  1. 第一次查完得到 ，第二次应该查 ，我写的
  2. 第一次查完得到 ， 可能等于 ，此时再查 会查出抽象东西。
  3. 带修莫队的询问编号编错了，导致答案存到了未知地方。
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
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e5+10,maxm=350;
int n,m,m1,m2,siz,tot;
int a[maxn],ans[maxn];
int st[maxm],ed[maxm],bel[maxn];
int cnt1[maxn],cnt2[maxm],cnt3[maxm];
struct query1{
    int pos,val;
}q1[maxn];
struct query2{
    int l,r,l1,r1,tim,id;
}q2[maxn];
inline bool cmp(query2 a,query2 b){return a.l/siz==b.l/siz?a.r/siz==b.r/siz?a.tim<b.tim:a.r<b.r:a.l<b.l;}
inline void init(){
    siz=sqrt(n);
    tot=n/siz;
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<n) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=n;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i;
}
inline void add(int x){
    if(!cnt1[x]) ++cnt3[bel[x]];
    ++cnt1[x];
    if(cnt1[x]%2==0) ++cnt2[bel[x]];
    else if(cnt1[x]%2==1&&cnt1[x]!=1) --cnt2[bel[x]];
}
inline void del(int x){
    --cnt1[x];
    if(!cnt1[x]) --cnt3[bel[x]];
    if(cnt1[x]%2==0&&cnt1[x]) ++cnt2[bel[x]];
    else if(cnt1[x]%2==1) --cnt2[bel[x]];
}
inline void move(int tim,int l,int r,int op){
    int pos=q1[tim].pos,val=q1[tim].val;
    if(pos>=l&&pos<=r) del(a[pos]);
    a[pos]+=val*op;
    if(pos>=l&&pos<=r) add(a[pos]);
}
inline int query2(int l,int r){
    if(l>r) return -1;
    int L=bel[l],R=bel[r];
    if(L==R){
        for(re int i=l;i<=r;++i) if(cnt1[i]) return i;
    }
    else{
        for(re int i=l;i<=ed[L];++i) if(cnt1[i]) return i;
        for(re int i=L+1;i<=R-1;++i){
            if(cnt3[i]){
                for(re int j=st[i];j<=ed[i];++j){
                    if(cnt1[j]) return j;
                }
            }
        }
        for(re int i=st[R];i<=r;++i) if(cnt1[i]) return i;
    }
    return -1;
}
inline int query(int l,int r){
    int L=bel[l],R=bel[r],pos=0;
    if(L==R){
        for(re int i=l;i<=r;++i) if(cnt1[i]%2==0&&cnt1[i]){pos=i;break;}
        if(pos) return query2(pos+1,r);
    }
    else{
        for(re int i=l;i<=ed[L];++i) if(cnt1[i]%2==0&&cnt1[i]){pos=i;break;}
        if(pos) return query2(pos+1,r);
        for(re int i=L+1;i<=R-1;++i){
            if(cnt2[i]){
                for(re int j=st[i];j<=ed[i];++j){
                    if(cnt1[j]%2==0&&cnt1[j]){pos=j;break;}
                }
            }
            if(pos) return query2(pos+1,r);
        }
        for(re int i=st[R];i<=r;++i)if(cnt1[i]%2==0&&cnt1[i]){pos=i;break;}
        if(pos) return query2(pos+1,r);

    }
    return -1;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1,op;i<=m;++i){
        cin>>op;
        if(op==1) ++m1,cin>>q1[m1].pos>>q1[m1].val;
        else ++m2,cin>>q2[m2].l>>q2[m2].r>>q2[m2].l1>>q2[m2].r1,q2[m2].tim=m1,q2[m2].id=m2;
    }
    siz=pow(n,2.0/3.0);
    sort(q2+1,q2+m2+1,cmp);
    init();
    int l=1,r=0,lst=0;
    for(re int i=1;i<=m2;++i){
        while(r<q2[i].r) add(a[++r]);
        while(l>q2[i].l) add(a[--l]);
        while(r>q2[i].r) del(a[r--]);
        while(l<q2[i].l) del(a[l++]);
        while(lst<q2[i].tim) move(++lst,l,r,1);
        while(lst>q2[i].tim) move(lst--,l,r,-1);
        ans[q2[i].id]=query(q2[i].l1,q2[i].r1);
    }
    for(re int i=1;i<=m2;++i) cout<<ans[i]<<'\n';
    return 0;
}

[BJWC2018] 基础匹配算法练习题

二分图匹配肯定是假的，先转化题意。

首先，把 转化成 。

令 ，转化为则 。

因为点的顺序不影响匹配，所以按点权从大到小排序，不难发现每个右部点对应的都是一段前缀。

现在问题转化为：给一个序列，每个点都有一个可供安排的前缀区域，每次区间查询，把该区间的点拿出来，最多能安排几个点。

首先想到莫队。

然后这东西想了半天没想出来怎么维护，最后发现可以线段树维护。

我们维护安排区域上的线段树。

每个节点上维护三个信息：区间大小（），区间内尝试过安排的数的个数（），区间内成功安排的数的个数（）。

指针移动时的修改就是单点修改。

贪心地，我们在这个点可供安排区域的右端点修改。

若该位置还未被匹配，则该点 和 +1，否则只有 +1。

删除是同理的。

然后考虑怎么合并信息。

关于合并， 直接相加即可。而 ，要先把左右相加，然后考虑能否多匹配几个。

这东西就是 ，也即是 。

可能会有疑问：为什么不把左边多的给右边？

因为我们每次都是贪心地把每个点插到自己的区域的右端点，所以肯定是右边会多。

复杂度

然而我用 upper_bound 传了个 greater 预处理每个点的安排区域写挂了，只有 95pts。

然后把这东西改成线段树上二分就行了。

呃呃，不知道哪里写错了，看来还是慎用 STL，尤其是不确定这么写会不会出问题的时候。

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
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=6e4+10,maxv=2e5+10;
int n,m,Q,z,siz,rt,segcnt;
int a[maxv],b[maxn],c[maxv];
int ans[maxn];
struct query{
    int l,r,id;
}q[maxn];
struct tree{
    int ls,rs,sum,ans,siz;
}tr[maxv<<1];
inline bool cmp(query a,query b){return ((a.l/siz)^(b.l/siz))?(a.l/siz)<(b.l/siz):((a.l/siz)&1)?a.r<b.r:a.r>b.r;}
inline void up(int p){
    tr[p].sum=tr[tr[p].ls].sum+tr[tr[p].rs].sum;
    tr[p].ans=tr[tr[p].ls].ans+tr[tr[p].rs].ans;
    tr[p].ans+=min(max(0ll,tr[tr[p].ls].siz-tr[tr[p].ls].ans),tr[tr[p].rs].sum-tr[tr[p].rs].ans);
}
inline void build(int l,int r,int &p){
    if(!p) p=++segcnt;
    tr[p].siz=r-l+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,tr[p].ls),build(mid+1,r,tr[p].rs);
}
inline void update(int l,int r,int pos,int val,int p){
    if(l==r){
        if(z-pos<a[l]) return;
        if(!tr[p].sum) tr[p].ans=1;
        tr[p].sum+=val;
        if(!tr[p].sum) tr[p].ans=0;
        return;
    }
    int mid=(l+r)>>1;
    if(z-pos<a[mid+1]) update(l,mid,pos,val,tr[p].ls);
    else update(mid+1,r,pos,val,tr[p].rs);
    up(p);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("std.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>z;
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1;i<=m;++i) cin>>b[i];
    sort(a+1,a+n+1);
    cin>>Q;
    for(re int i=1;i<=Q;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    siz=sqrt(m);
    sort(q+1,q+Q+1,cmp);
    build(1,n,rt);
    int l=1,r=0;
    for(re int i=1;i<=Q;++i){
        while(r<q[i].r) update(1,n,b[++r],1,1);
        while(l>q[i].l) update(1,n,b[--l],1,1);
        while(r>q[i].r) update(1,n,b[r--],-1,1);
        while(l<q[i].l) update(1,n,b[l++],-1,1);
        ans[q[i].id]=tr[1].ans;
    }
    for(re int i=1;i<=Q;++i) cout<<ans[i]<<'\n';
    return 0;
}