题解 P9969 [THUPC 2024 初赛] 分治乘法
不会做，但是乱搞过了。
直接分治乘或合并果子面对五十万个 1 要操作九百九十七万次，几乎是题目限制的两倍，但这已经是前两个操作的最优结果，所以考虑用第三个操作进行优化。
有一个很 naive 的想法是把所有长度为二的连续段的第一个元素用操作一构造出来，再用操作三平移构造第二个元素，最后合并果子。在 1 很稠密的时候这个东西确实能优化很多，但是仍然会被五十万个 1 薄纱。。。
五十万个 1 疑似有点极端稠密了。。。于是我们也极端一点，把长度为三的连续段也用前述方式构造出来再合并果子，注意控制好阈值，然后这个东西薄纱五十万个 1 了。。。然后在五十万个 1 里随机加 0 拍了一千组也轻松薄纱。。。然后交上去过了。
实际上这个阈值貌似瞎取也没太大问题。
不会证也不会 hack，给出参考代码供大家薄纱。
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#define ALL(v) v.begin(),v.end()
#define For(i,_) for(int i=0,i##end=_;i<i##end;++i) // [0,_)
#define FOR(i,_,__) for(int i=_,i##end=__;i<i##end;++i) // [_,__)
#define Rep(i,_) for(int i=(_)-1;i>=0;--i) // [0,_)
#define REP(i,_,__) for(int i=(__)-1,i##end=_;i>=i##end;--i) // [_,__)
typedef long long ll;
typedef unsigned long long ull;
#define V vector
#define pb push_back
#define pf push_front
#define qb pop_back
#define qf pop_front
#define eb emplace_back
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
#define fi first
#define se second
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}},inf=0x3f3f3f3f,mod=1e9+7;
const ll infl=0x3f3f3f3f3f3f3f3fll;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
int init=[](){return cin.tie(nullptr)->sync_with_stdio(false),0;}();
#ifdef ONLINE_JUDGE
static char pbuf[1000000],*p1=pbuf,*p2=pbuf,obuf[1000000],*o=obuf;
#define getchar() p1==p2&&(p2=(p1=pbuf)+fread(pbuf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (o-obuf<1000000)?(*o++=(x)):(fwrite(obuf,o-obuf,1,stdout),o=obuf,*o++=(x))
struct flusher{~flusher(){fwrite(obuf,o-obuf,1,stdout);}}autoflush;
#endif
inline int qr(){
int in=0;char ch;
while(!isdigit(ch=getchar()));
do in=(in<<1)+(in<<3)+(ch^48);while(isdigit(ch=getchar()));
return in;
}
template<class T>
void qw(T out){
if(out>9)qw(out/10);
putchar(out%10|48);
}
inline char gc(){
char ch;
while(!isupper(ch=getchar()));
return ch;
}
int main(){
int n=qr();
V<char>a;
a.reserve(n);
char ch;
while(!isdigit(ch=getchar()));
do a.pb(ch);while(isdigit(ch=getchar()));
V<V<int>>ans;
V<int>siz;
auto cmp=[&](int x,int y){return siz[x]>siz[y];};
priority_queue<int,V<int>,decltype(cmp)>q(cmp);
if(count(ALL(a),49)>=300000){
priority_queue<int,V<int>,decltype(cmp)>_q(cmp);
For(i,n-2)if((a[i]^48)&&(a[i+1]^48)&&(a[i+2]^48))a[i]=a[i+1]=a[i+2]=48,ans.pb({1,i+1}),siz.pb(1),_q.push(ans.size()-1);
while(_q.size()>1){
int x=_q.top();_q.pop();
int y=_q.top();_q.pop();
ans.pb({2,x+1,y+1}),siz.pb(siz[x]+siz[y]),_q.push(ans.size()-1);
}
int nw=ans.size();
ans.pb({3,nw,1}),siz.pb(siz[nw-1]);
ans.pb({3,nw+1,1}),siz.pb(siz[nw]);
ans.pb({2,nw,nw+1}),siz.pb(siz[nw-1]+siz[nw]);
ans.pb({2,nw+2,nw+3}),siz.pb(siz[nw+1]+siz[nw+2]);
q.push(nw+3);
}
if(count(ALL(a),49)>=150000){
priority_queue<int,V<int>,decltype(cmp)>_q(cmp);
For(i,n-1)if((a[i]^48)&&(a[i+1]^48))a[i]=a[i+1]=48,ans.pb({1,i+1}),siz.pb(1),_q.push(ans.size()-1);
while(_q.size()>1){
int x=_q.top();_q.pop();
int y=_q.top();_q.pop();
ans.pb({2,x+1,y+1}),siz.pb(siz[x]+siz[y]),_q.push(ans.size()-1);
}
int nw=ans.size();
ans.pb({3,nw,1}),siz.pb(siz[nw-1]);
ans.pb({2,nw,nw+1}),siz.pb(siz[nw]<<1);
q.push(nw+1);
}
For(i,n)if(a[i]^48)ans.pb({1,i+1}),siz.pb(1),q.push(ans.size()-1);
while(q.size()>1){
int x=q.top();q.pop();
int y=q.top();q.pop();
ans.pb({2,x+1,y+1}),siz.pb(siz[x]+siz[y]),q.push(ans.size()-1);
}
qw(ans.size()),putchar(10);
for(auto &i:ans){
for(int j:i)qw(j),putchar(32);
putchar(10);
}
return 0;
}