YbtOJ #772. 「分块算法」密码破译
本文最后更新于 101 天前,其中的信息可能已经有所发展或是发生改变。

题目链接:YbtOJ #772

你有一个 $n$ 列,无穷行的表格,每个格子上都有一个正整数,第 $i$ 行第 $j$ 列的数为 $a_{i,j}$。我们通过如下方法来构造这个表格:

  • $a_{1,i}$ 在输入中直接给出。
  • $\forall i>1,j\in [1,n],a_{i,j}=\sum_{k=1}^j[a_{i-1,k}=a_{i-1,j}]$。

你需要依次执行 $m$ 个操作,操作有以下两种形式:

  • 1 v i:将 $a_{1,i}$ 的值改为 $v$,并将表格重新构造。
  • 2 x y:询问 $a_{x,y}$ 的值。

对于每个询问,你需要输出对应的结果。

$1\leq n,m\leq 10^5,1\leq a_{1,i},v\leq 10^5$。

Solution

被 fxt 拉来写分块/cy。

很容易注意到偶数行全部相同,奇数行除了第 $1$ 行都相同。

先考虑偶数行怎么做,先序列分块。设 $s[i][j]$ 表示前 $i$ 块数 $j$ 的出现次数。

修改的时候暴力修改 $k\sim tot$ 块,查询的时候整块直接查,散块暴力即可。

显然这东西很好维护,时间复杂度 $O(S)$。

再考虑奇数行,注意到偶数行每种 $a_i$ 对应的位置上数字为 $1,2,3,\cdots,x$。

我们可以设 $c[i][j]$ 表示前 $i$ 块,出现次数超过 $j$ 的数的种类。

修改的时候同样暴力修改,只需要关注恰好到达 $j$ 的位置即可。

查询的时候整块直接查,散块暴力,时间复杂度 $O(S)$。

显然修改的常数会很大,所以可以把块长略微调大。

Code

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,M=1e4+10,BM=sqrt(N)+5;
int n,m,S,a[N],tot,bl[N],L[BM],R[BM],s[BM][M],c[BM][N],cp[M];
I void U(CI p,CI v){if(a[p]==v) return ;RI i;for(i=bl[p];i<=tot;i++) --c[i][s[i][a[p]]--],++c[i][++s[i][v]];a[p]=v;}
I int Q1(CI x){RI i,X=s[bl[x]-1][a[x]];for(i=L[bl[x]];i<=x;i++) X+=(a[i]==a[x]);return X;}
I int Q2(CI x){RI i,t=Q1(x),X=c[bl[x]-1][t];for(i=L[bl[x]];i<=x;i++) X+=((++cp[a[i]])+s[bl[x]-1][a[i]]==t);for(i=L[bl[x]];i<=x;i++) --cp[a[i]];return X;}
int main(){
    freopen("password.in","r",stdin),freopen("password.out","w",stdout);
    RI i,j,o,x,y;for(read(n),S=min((int)sqrt(n)*3,n),i=1;i<=n;i++) read(a[i]),!((i-1)%S)&&(R[tot]=i-1,L[++tot]=i),bl[i]=tot;R[tot]=n;
    for(i=1;i<=tot;i++){for(j=0;j<M;j++) s[i][j]=s[i-1][j];for(j=0;j<=n;j++) c[i][j]=c[i-1][j];for(j=L[i];j<=R[i];j++) ++c[i][++s[i][a[j]]];}
    for(read(m);m--;) read(o,x,y),o&1?U(y,x):writeln(x^1?x&1?Q2(y):Q1(y):a[y]);return 0;
}

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇