AGC047E Product Simulation

简单构造，不过做着挺有趣的。

首先可以问 $0 < A$ 造 $1$ ，就算是 $0$ 也没关系，是 $0$ 的话之后得到的所有数都是 $0$ 了。

然后可以造出 $2^0 \sim 2^{29}$ ，放到固定的一些位置中。

然后我们考虑造出对 $k = 0\sim 29$ ，判断 $B$ 在这一位是否有值。从高到低考虑每一位，用一个位置 $x$ 来维护 $B$ 之前的位的和。对于当前位 $t$ ，我们把 $x$ 先加上 $2^t$ ，然后把这个数和 $B$ 比较一下，把结果放到一个位置 $c$ 。然后我们可以直接给 $c$ 通过自加得到 $c2^t$ ，把这个数加到 $x$ 上，就可以完成 $x$ 的维护。

现在的问题是，我们需要实现如果 $c$ 有值，就给答案加上 $A2^t$ 。我的做法是先通过 $c<1$ 给 $c$ 取反，然后自加 $30$ 次得到 $(!c)2^{30}$ 。接下来我们用同样的方法对 $A$ 做拆分，但是把原来的 $x + 2^t$ 与 $A$ 比较变成 $x+2^t+c$ 与 $A$ 比较。此时，如果 $c$ 原来无值一定比较失败，对 $x$ 加 $0$ ，如果原来有值就会正常进行比较。这样就可以得到一个当 $c$ 为 $0$ 则为 $0$ ，否则为 $A$ 的数，我们给这个数自加 $t$ 次加到答案上就行了。

这样就构造了 $O(\log^3 n)$ 的一个方案，如果压一下可以做到 $O(\log ^2n)$ ，但是没什么意思。

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
// #pragma GCC optimize(2)
typedef long long ll;
const int MAXN = 1e6 + 10;
const int P = 1e9 + 7;

struct op {
    int o , a , b , c;
};
vector<op> ops;

ll reg[MAXN];
void sum( int i , int j , int k ) {
    ops.pb( (op) { 0 , i , j , k } );
    ll re = reg[i] + reg[j];
    reg[k] = re;
}

void jud( int i , int j , int k ) {
    ops.pb( (op) { 1 , i , j , k } );
    int re = reg[i] < reg[j];
    reg[k] = re;
}

void solve() {
    reg[0] = 13224 , reg[1] = 535342;
    jud( 2 , 0 , 3 );
    int td = 3;
    rep( i , 1 , 29 ) {
        sum( td + i - 1 , td + i - 1 , td + i );
    }
    sum( 0 , td , 0 ) , sum( 1 , td , 1 );
    int tr = td + 30 + 2 , tp = tr + 30 + 2;
    int ga = tp + 5;
    per( k , 29 , 0 ) {
        sum( tp , td + k , tp + 1 );
        jud( tp + 1 , 1 , tr + k );
        rep( t , 1 , k ) sum( tr + k , tr + k , tr + k );
        sum( tr + k , tp , tp );
        sum( tr + k , 10000 , ga + 1 );
        jud( ga + 1 , td , ga + 1 );
        rep( p , 1 , 30 ) sum( ga + 1 , ga + 1 , ga + 1 );
        jud( ga + 3 , ga + 3 , ga + 3 );
        per( t , 29 , 0 ) {
            sum( ga + 3 , td + t , ga + 2 );
            sum( ga + 2 , ga + 1 , ga + 2 );
            jud( ga + 2 , 0 , ga + 4 );
            rep( k , 1 , t ) sum( ga + 4 , ga + 4 , ga + 4 );
            sum( ga + 4 , ga + 3 , ga + 3 );
        }
        rep( t , 1 , k ) sum( ga + 3 , ga + 3 , ga + 3 );
        sum( ga , ga + 3 , ga );
        // if( k == 0 ) {
        //     cout << reg[ga] << ' ' << reg[tr + k] << endl;
        // }
    }
    sum( ga , 10000 , 2 );
    cout << ops.size() << endl;
    // cout << reg[2] << endl;
    for( auto t : ops ) {
        if( t.o ) printf("< %d %d %d\n",t.a,t.b,t.c);
        else printf("+ %d %d %d\n",t.a,t.b,t.c);
    }
}

signed main() {
//	 freopen("in","r",stdin);
	// freopen("fout","w",stdout);
	// int T;cin >> T;while( T-- ) solve();
	solve();
}