ps:用來監督自己補題
F Fake Maxpooling
題意:給一個nm的矩陣，求所有kk的子矩陣中最大值的的和
思路：
橫豎兩遍單調隊列就秒了，一瞬間就想到了，但是O(n*m log)以為鐵T，看到還以為是數學題，就打表找了很久規律，結果過的人越來越多，就上去秒了
學到了出題人一個很牛掰的方法，具體思路其實就是和歐拉篩一樣，篩倍數，是O(nm loglog),這樣就比較穩了，其實應該是可以線性篩O(nm)，隻是比較麻煩而已
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5005;
int a[maxn][maxn],q[maxn],head,tail,f[maxn][maxn];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main()
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(!a[i][j])
for(int k=1;k*i<=n&&k*j<=m;++k)
a[k*i][k*j]=k;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
a[i][j]=i*j/a[i][j];
int cnt=0;
for(int j=1;j<=m;++j)
{
cnt=0;
head=1,tail=0;
for(int i=1;i<=n;++i)
{
while(head<=tail&&a[i][j]>=a[q[tail]][j])tail--;
q[++tail]=i;
if(i-q[head]+1>k)head++;
if(i>=k)f[++cnt][j]=a[q[head]][j];
}
}
ll ans=0;
for(int i=1;i<=cnt;++i)
{
head=1,tail=0;
for(int j=1;j<=m;++j)
{
while(head<=tail&&f[i][j]>=f[i][q[tail]])tail--;
q[++tail]=j;
if(j-q[head]+1>k)head++;
if(j>=k)ans+=f[i][q[head]];
}
}
printf("%lld\n",ans);
return 0;
}
G.Greater and Greater
題意：給出兩個序列 A、B，其長度分别為 n、m，保證 n>m ，求 A 中有多少個長度為 m 的子串 S，使得∀i∈{1,2,⋯,m},Si≥Bi
思路：
這題我補了很久，盡量用通俗的語言講，首先對于每個Ai維護一個長度為bitset，Si[j]=1當且僅當Ai>=Bj,如下圖，我們發現，其實本質隻有m+1種這樣的bitset，他們取決于該數字在排序後的數字的位置，對B排序後的bitset Si我們可以發現，Si+1和第Si唯一的差别就是在對應的原來的id的位置設定為1
這樣我們很容易可以預處理出所有Si,那麼怎麼求出ans呢，如下圖，發現當一豎列都為1的時候，可以對答案貢獻，是以我們隻需要倒序将si不斷左移并且&上s(i-1)即可，具體來說，就是用一個curi,
為什麼要或上第m位為1的數呢，因為左移的時候，是為了防止後面的數不被影響，即隻受所&的數的影響，還要吐槽一句，我從沒用過bitset，這裡的左移，居然是>>,調了我4h
H.Happy Triangle
題意：給你一個multiset，三種操作
1.加入x
2.删去x
3.給出一個x，問能否在multiset中找到另外兩個元素a,b，a可以等于b，使得三者可以構成一個非退化三角形
思路：
假設a<=b,則x可能是最大值，次大值，最小值
1.如果是最大值的話，隻需要<=x的最大的兩個a,b可以就行了
2.如果是次大值，則x加上x的前驅>x的字尾就行了
3.最小值的話，隻需要abs|a-b|<x即可，最優情況下就是相鄰的兩個數
我們來捋一捋，我們需要一個資料結構，支援增删，查找集合中的相鄰的數最小值，根據增删單點修改最小值，不難想到，隻要離散化+權值線段樹即可，樹上維護相鄰的最小內插補點，我是轉為離線操作再處理
#include<bits/stdc++.h>
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define ls p<<1
#define rs p<<1|1
using namespace std;
multiset<int>s;
const int maxn=2e5+7;
const int inf=2e9+5;
const int INF=0x3f3f3f3f;
int tr[maxn<<2],op[maxn],a[maxn],b[maxn],q,cnt[maxn];
void build(int p,int l,int r)
{//一開始初始化為最大值
tr[p]=inf;
if(l==r)return;
int mid=l+r>>1;
build(lson);
build(rson);
}
void update(int p,int l,int r,int pos,int val)
{
if(l==r){
tr[p]=val;
return;
}
int mid=l+r>>1;
if(pos<=mid)update(lson,pos,val);
else update(rson,pos,val);
tr[p]=min(tr[ls],tr[rs]);
}
int query(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return tr[p];
int mid=l+r>>1,ans1=inf,ans2=inf;
if(L<=mid)ans1=query(lson,L,R);
if(R>mid)ans2=query(rson,L,R);
return min(ans1,ans2);
}
int main()
{
s.insert(-INF);s.insert(-INF);//正負無窮作為哨兵
s.insert(inf);
scanf("%d",&q);
for(int i=1;i<=q;++i)
scanf("%d%d",&op[i],&a[i]),b[i]=a[i];
sort(a+1,a+1+q);
int len=unique(a+1,a+1+q)-(a+1);
build(1,1,len);
for(int i=1;i<=q;++i)
{
if(op[i]==1){
s.insert(b[i]);
int x=lower_bound(a+1,a+1+len,b[i])-a;
cnt[x]++;
if(cnt[x]==1){//隻有一個的時候是上一個和目前的內插補點
update(1,1,len,x,*s.upper_bound(b[i])-b[i]);
auto it=s.lower_bound(b[i]);
it--;
int tmp=*it;
int y=lower_bound(a+1,a+1+len,tmp)-a;
if(cnt[y]==1)update(1,1,len,y,b[i]-tmp);//隻有上一個數隻剩一個的時候才更新
}
else if(cnt[x]==2)update(1,1,len,x,0);//因為如果超過1個，最小內插補點肯定是0
}
else if(op[i]==2) {
s.erase(s.find(b[i]));
int x=lower_bound(a+1,a+1+len,b[i])-a;
cnt[x]--;
if(cnt[x]==1)update(1,1,len,x,*s.upper_bound(b[i])-b[i]);//删到隻剩一個的時候更新
else if(!cnt[x]){ //删沒的時候要更新前面那個
update(1,1,len,x,inf);
auto it=s.lower_bound(b[i]);
it--;
int tmp=*it;
int y=lower_bound(a+1,a+1+len,tmp)-a;
if(cnt[y]==1)update(1,1,len,y,*s.lower_bound(b[i])-tmp);
}
}
else{
bool flag=0;
auto it=s.lower_bound(b[i]);
int t1=*it,t2=*(--it),t3=*(--it);
int x=lower_bound(a+1,a+1+len,b[i])-a;
if(t2+t3>b[i]||t2+b[i]>t1)flag=1;//判斷第一種和第二種能否成三角形
if(query(1,1,len,x,len)<b[i])flag=1;//第三種查詢最小內插補點
if(flag)puts("Yes");
else puts("No");
}
}
return 0;
}
J.Just Shuffle
題意：
初始是1 2…n，給你一個置換函數 f^k之後得到的數列，問 f 是什麼，繼續背鍋…一開始我記得我的置換定義是沒有錯的，但是自己傻叉了手推樣例的時候推不對，以為自己錯了，結果聽老闆搞了個錯的題意，居然還可以推出來樣例，後面自閉3h推不出，一開始我就往同餘想了，結果自己sb手寫樣例還算錯，無語了
思路：
首先得搞懂置換是什麼東西，其實可以看成是一一映射，舉例來說，如下圖。
知道置換是什麼東西就好搞了，事實上，對于一個置換，我們會産生一些環，也就是經過一段周期後回到初始位置，我們設答案 F這個函數形成的環的 size分别為 sz1,sz2…我們發現，其實我們已知F走k到達的點，現在求每個點走第一步到達的點，由于k是個大質數，是以有以下做法
簡單來說就是在F^k上走inv(k,size (F ^k))步走到的地方就等于答案，是以根據輸入構造下環求個逆元就秒了
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int a[maxn],ans[maxn],x,y;
bool v[maxn];
int exgcd(int a,int b,int &x,int &y){
if(!b){ x=1,y=0;return a;}
int d=exgcd(b,a%b,x,y);
int z=x;x=y;y=z-y*(a/b);
return d;
}
int inv(int k,int size){
exgcd(k,size,x,y);
return (x%size+size)%size;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i){
if(v[i])continue;
vector<int>tmp;
tmp.pb(i);v[i]=1;
int now=a[i];
while(now!=i){
tmp.pb(now);v[now]=1;
now=a[now];
}
int sz=tmp.size();
int ni=inv(k,sz);
for(int i=0;i<sz;++i)
ans[tmp[i]]=tmp[(i+ni)%sz];
}
for(int i=1;i<=n;++i)
printf("%d ",ans[i]);
return 0;
}