ZeroJudge f999 - SCP - A 特訓班 解題心得( 題目 )
閒話家常:最近在處理discord的bot問題，好久沒寫這種扣了。
解題概念:分治、DSU
解題方法:這題是個蠻特別的題目，是becaido出的、我覺得算好題，需要多個技巧解題，我甚至寫了一個解題方法: https://hackmd.io/@r1cky/rJ06V5sL5。
-首先是問題的reduce，這題是環狀看起來很可怕，不過其實不要把他想成環狀就好了
-他一開始的編碼感覺很複雜，但把編碼重新編一次就舒服多了，本來兩個陣列消到剩下一個。
-接著怎麼想到它可以等價於某個經典題呢?感謝lai alan之前把資芽的習題給我看，看了我才想到可以把這題當成那題，不過那題需要再做一次reduce才會可做。
其實我一開始只想到三次方的方法，後來發現DSU可以降一維但不夠，之後不要把問題看成環狀其實就是O(NlogN)的分治了，而環狀就是用DSU特別做多一種case即可。
註:另外聽作者說這題也可以使用懶標線段樹解，似乎也是同樣複雜度，所以也算是個解法多樣化的題目。
Java參考程式碼(有更好意見可留言於下方，謝謝!):
//Author:En Chi Tsung(欉恩祁)
//Date:2022/05/13
import java.io.*;
import java.util.*;
public class Main implements Runnable{
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,rd,top;
public static final int ad=200000;
public static long ans=0;
public static int[] a=new int[100005];
public static int[] c=new int[100005];
public static int[] rc=new int[100005];
public static int[] xx=new int[400005];
public static int[] xo=new int[400005];
public static int[] oo=new int[400005];
public static int[] min=new int[100005];
public static int[] max=new int[100005];
public static int[] dsu=new int[100005];
public static int[] pre=new int[100005];
public static int[] big=new int[100005];
public static void main(String[] args) throws Exception{
new Thread(null,new Main(),"",1<<26).start();
}
public void run() {
final int n=readint();
if(n==1) {
System.out.println(1);
System.exit(0);
}
for(int i=1;i<=n;i++) {
a[i]=readint();
}
for(int i=1;i<=n;i++) {
c[i]=readint();
rc[c[i]]=i;
}
for(int i=1;i<=n;i++) {
c[rc[a[i]]]=i;
}
ArrayList<Integer> r=new ArrayList<>();
for(int i=1;i<=n;i++) {
r.add(c[i]);
if(c[i]==n)break;
}
int idx=1;
for(int i=r.size()+1;i<=n;i++) {
c[idx++]=c[i];
}
for(int i:r) {
c[idx++]=i;
}
DAC(1,n-1);
dsu[n]=n;
head=n;
for(int i=1;i<=n;i++) {
rc[c[i]]=i;
}
for(int i=n,j=1;i>0;i--,j++) {
dsu[i]=i;
big[i]=1;
if(rc[i]==1) {
onion(c[1],c[n]);
}
else if(dsu[c[rc[i]-1]]>0) {
onion(c[rc[i]-1],i);
}
if(i!=n&&dsu[c[rc[i]+1]]>0) {
onion(c[rc[i]+1],i);
}
if(big[n]==j) {
ans++;
}
}
System.out.println(ans);
}
public static void onion(int s,int f) {
go(s);
int ta=top;
go(f);
int tb=top;
if(ta>tb) {
int tmp=ta;
ta=tb;
tb=tmp;
}
if(ta==tb)return;
big[tb]+=big[ta];
big[ta]=0;
dsu[ta]=dsu[tb];
}
public static void go(int x) {
if(dsu[x]==x) {
top=x;
return;
}
go(dsu[x]);
dsu[x]=top;
}
public static void DAC(int l,int r) {
if(l==r) {
ans++;
return;
}
final int mid=(l+r)>>1;
int lp=mid;
int hp=mid;
int mun=(1<<30);
int mux=-mun;
DAC(l,mid);
DAC(mid+1,r);
for(int i=mid+1;i<=r;i++) {
mun=Math.min(mun,c[i]);
mux=Math.max(mux,c[i]);
min[i]=mun;
max[i]=mux;
xx[mux-mun-i+ad]++;
pre[i]=mux-mun-i+ad;
}
mun=(1<<30);
mux=-mun;
for(int i=mid;i>=l;i--) {
mun=Math.min(mun,c[i]);
mux=Math.max(mux,c[i]);
while(lp!=r&&min[lp+1]>mun) {
lp++;
if(lp>hp) {
xx[pre[lp]]--;
pre[lp]=max[lp]-lp+ad;
xo[pre[lp]]++;
}
else {
xo[pre[lp]]--;
pre[lp]=-lp+ad;
oo[pre[lp]]++;
}
}
while(hp!=r&&max[hp+1]<mux) {
hp++;
if(hp>lp) {
xx[pre[hp]]--;
pre[hp]=-min[hp]-hp+ad;
xo[pre[hp]]++;
}
else {
xo[pre[hp]]--;
pre[hp]=-hp+ad;
oo[pre[hp]]++;
}
}
ans+=xx[-i+ad];
ans+=xo[-i-mux+ad];
ans+=xo[mun-i+ad];
ans+=oo[-i+mun-mux+ad];
}
while(lp!=r) {
lp++;
if(lp>hp) {
xx[pre[lp]]--;
pre[lp]=max[lp]-lp+ad;
xo[pre[lp]]++;
}
else {
xo[pre[lp]]--;
pre[lp]=-lp+ad;
oo[pre[lp]]++;
}
}
while(hp!=r) {
hp++;
if(hp>lp) {
xx[pre[hp]]--;
pre[hp]=-min[hp]-hp+ad;
xo[pre[hp]]++;
}
else {
xo[pre[hp]]--;
pre[hp]=-hp+ad;
oo[pre[hp]]++;
}
}
for(int i=mid+1;i<=r;i++) {
oo[pre[i]]=0;
}
}
public static int readint(){
try {
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
return ret;
}
catch(Exception e) {
return -1;
}
}
}
文章標籤
全站熱搜
留言列表
