T1. 春江潮水连海平

将所有排水口按照 $t_i$ 排序。依次插入一个按 $h_i$ 排序的大根堆。

每次判断是先弹出一个堆顶的排水口，还是插入下一个排水口，依题意模拟即可。

复杂度 $O(n\log n)$

#include<bits/stdc++.h>
using namespace std;

// #define int long long
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fi first
#define se second

const int N = 1e5+5;
const int M = (1<<8)+5;;
const ll inf = 5e18+5;
const int p = 998244353;

int h,n;
pii a[N];

signed main(){
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
    // ios::sync_with_stdio(false); cin.tie(0u); cout.tie(0u);
    cin >> h >> n;

    bool ok = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i].fi >> a[i].se;
        if (!a[i].se) ok = 1;
    }
    if (!ok){
        cout << "-1\n";
        return 0;
    }

    sort(a+1,a+n+1);
    
    db ans = 0;
    db now = h;
    
    priority_queue<int> q; 
    for (int i = 1; i <= n; i++){
        if (a[i].se >= now) continue;
        bool tt = 1;
        while (ans < a[i].fi){ // 当前时间
            if (q.size()){ 
                if (ans+(db)(now-q.top())/q.size() < a[i].fi){ // 到插入的下一个位置 之前到不了当前时间
                    ans += (db)(now-q.top())/q.size();
                    now = q.top();
                    q.pop();
                }else{ // 到插入的下一个位置 超越当前时间
                    // cout << i << endl;
                    db t = (db)(a[i].fi-ans)*q.size(); // 到当前时间，能走多远
                    now -= t;
                    ans = a[i].fi;
                }
            }else{
                ans = a[i].fi;
            }
            if (!now){
                printf("%.6Lf", ans);
                return 0;
            }
        }
        // cout << i << " " << ans << " " << now << '\n';
        if (now > a[i].se) q.push(a[i].se);
        // while(q.size() && q.top() > now) q.pop(); 
    }

    while(q.size()){
        ans += (now-q.top())/q.size();
        now = q.top();
        q.pop();
    }
    printf("%.6Lf", ans);

    
	return 0;
}

T2. 落月摇情满江树

容易发现想要离开一个子树，只有可能从子树的根，或最左边的叶子（以下称左），或最右边的叶子离开（以下称右）。

一个环想要通过一个子树，只有可能是从根走到左、根走到右、左走到右、当前子树已经满足题目条件，可以用若干个环覆盖这四种情况。

我们可以设计状态 $f[i][0/1/2/3]$ 。

$f[i][0]：$ 当前子树可以用若干个环与一条从根到左的路径表示。

$f[i][1]：$ 当前子树可以用若干个环与一条从根到右的路径表示。

$f[i][2]：$ 当前子树可以用若干个环与一条从左到右的路径表示。

$f[i][3]：$ 当前子树可以用若干个环表示。

依次转移即可，复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int n;

vector<int> v[N];
bool f[N][4];
void dfs(int x){
    int sz = v[x].size();
    if (!sz){
        f[x][1] = f[x][2] = f[x][3] = 1;
        return;
    } 
    for (int y:v[x]){
        dfs(y);
    } 

    int pl0 = -1, pr0 = sz; 
    int pl3 = -1, pr3 = sz;
    
    while(pl0 < sz-1 && f[v[x][pl0+1]][0]) pl0++;
    while(pl3 < sz-1 && f[v[x][pl3+1]][3]) pl3++;
    while(pr0 > 0 && f[v[x][pr0-1]][0]) pr0--;
    while(pr3 > 0 && f[v[x][pr3-1]][3]) pr3--;

    int lst1 = -1, lst2 = -1; 
    for (int i = 0; i < sz; i++){
        int y = v[x][i];
        if (f[y][2] && lst1 != -1 && lst1-1 <= pl3 && i+1 >= pr3) f[x][3] = 1; 
        if (!f[y][0]) lst1 = -1; 
        if (f[y][1] && lst1 == -1) lst1 = i;  

        if (f[y][1] && lst2 != -1 && lst2-1 <= pl0 && i+1 >= pr0) f[x][0] = 1;
        if (!f[y][3]) lst2 = -1;
        if (f[y][2] && lst2 == -1) lst2 = i; 
    }

    
    for (int i = 0; i < sz; i++){ 
        int y = v[x][i];
        if (f[y][1] && i+1 >= pr0 && i-1 <= pl3) f[x][1] = 1;
        if (f[y][2] && i+1 >= pr3 && i-1 <= pl0) f[x][2] = 1;
    }
}

int T;
signed main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0u); cout.tie(0u);
    cin >> T;
    while(T--){
        cin >> n;
        for (int i = 1; i <= n; i++){
            f[i][0] = f[i][1] = f[i][2] = f[i][3] = 0;
            v[i].clear();
        } 
        for (int i = 1; i <= n; i++){
            int k;
            cin >> k;
            for (int j = 1; j <= k; j++){
                int x;
                cin >> x;
                v[i].push_back(x);
            }
        }
        dfs(1);
        if (f[1][0]) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    return 0;
}

T3. 禁止套娃

题意

求一个序列的所有本质不同子序列的本质不同子序列个数之和 $\bmod 1000000007$。$n\le 5000$。

算法一

计算一个序列的本质不同子序列个数的方法如下：

由于会计重，考虑对于每一种子序列，钦定只对它最靠左（贪心）的匹配计数。容易证明存在唯一的这样的子序列到下标的映射。

令 $dp_i$ 表示末尾选 $i$ 的本质不同子序列数，则 $dp_0=1,dp_i=\sum_{j=pre_i}^{i-1}dp_j$，$pre_i$ 表示上一个与 $a_i$ 相等的位置，如果不存在则为 $0$。

或者，令 $dp_i$ 表示末尾选 $\le i$ 的本质不同子序列数，则 $dp_0=1,dp_i=2dp_{i-1}-dp_{pre_i-1}$。

外层暴枚可做到 $\mathrm{O}(n2^n)$，期望得分 $30$。

算法二

直接讲正解。

设选择的外层子序列下标为集合 $I$，内层为集合 $J\subseteq I$。为了方便表述，设占位下标 $0\in I,J$。同样只计贪心匹配的情况，限制如下：

1. $I$ 中相邻两个数 $i,i'$，$a_{i+1\sim i'-1}$ 中不存在 $=a_{i'}$ 的值。
2. $J$ 中相邻两个数 $j,j'$，$a_{I\cap(j,j')}$ 中不存在 $=a_{j'}$ 的值。

考虑对 $J$ dp。$f_i$ 表示目前考虑到 $i$ 且内外层末尾均选 $i$ 的答案。如果要从 $f_j$ 转移过来，那么就要决定 $a_{j+1\sim i-1}$ 这部分如何选外层，设选择了集合 $K$，限制如下；

1. $K$ 中相邻两个数 $k,k'$，$a_{k+1\sim k'-1}$ 中不存在 $=a_{k'}$ 的值。
2. $K$ 中最大值 $k_r$，$a_{k_r+1\sim i-1}$ 中不存在 $=a_i$ 的值。
3. $K$ 中任意 $k$，$a_k\ne a_i$。

一个简洁的处理方法是，对于每一个 $i$，dp 出 $>$ 每个 $j$ 的只需满足 1、3 条件的本质不同子序列个数 $g_{i,j}$，真正转移时 $f_i\xleftarrow{+}(g_{i,j}-g_{pre_i,j})\cdot f_j$ 即可。最后汇总答案可以弄一个必选的占位下标 $n+1$。

$g$ 是 2D/0D，$f$ 是 1D/1D，时间复杂度 $\mathrm{O}(n^2)$，期望得分 $100$。

如果您想到了低于平方的解法，请联系 YeahPotato！

#include <bits/stdc++.h>
using namespace std;
#define P 1000000007
int n, a[5005], now[5005], f[5005], g[5005][5005];
int R(int x, int y) { return (x += y) >= P ? x - P : x; }
int main() {
	freopen ("nest.in", "r", stdin);
	freopen ("nest.out", "w", stdout);
	cin >> n;
	for (int i=1; i<=n; i++)
		scanf ("%d", &a[i]);
	for (int i=1; i<=n+1; i++) {
		g[i][i] = 1;
		for (int j=i-1; j; j--) {
			g[i][j] = g[i][j+1];
			if (a[j] ^ a[i]) g[i][j] = R(g[i][j], R(g[i][j+1], now[a[j]] ? P - g[i][now[a[j]]+1] : 0));
			now[a[j]] = j;
		}
		for (int j=i-1; j; j--)
			now[a[j]] = 0;
	}
	f[0] = 1;
	for (int i=1; i<=n+1; i++) {
		for (int j=0; j<i; j++)
			f[i] = (f[i] + 1ll * (g[i][j+1] + P - g[now[a[i]]][j+1]) * f[j]) % P;
		now[a[i]] = i;
	}
	cout << f[n+1];
}

T4. presuffix

非常直观的感觉，操作次数不会特别的多，考虑证明上界为 $3$。

令 $a_i$ 为给定的数组，$s_i$ 为 $a_i$ 的前缀和，令 $s_x,s_y$ 分别为 $s_i$ 的最小值和最大值。

• 若 $x \gt y$，则用操作 $1$ 令 $x \lt y$。
• 不妨令 $s_x \lt 0,s_y \gt 0$，先用操作 $2$ 操作 $[x+1,n]$，被操作的所有数 $u$ 会变成 $s_u-s_x$，是非负的，因为 $s_x \lt 0$，故最大值的位置仍然在 $[x+1,n]$ 中，令 $y$ 为新的最大值出现位置，用操作 $3$ 操作 $[1,y]$，被操作的所有数 $v$ 会变成 $s_y-s_{v-1}$，同样非负。

分情况讨论：

若答案为 $0$，当且仅当所有 $a_i \ge 0$。

若答案为 $1$，不妨要么进行一次 $1$ 操作，要么存在一个区间满足前/后缀和 $\ge 0$，且区间外的所有数 $\ge 0$。而在区间左右两端加上非负数是不劣的，故只要判断前/后缀和数组是否都 $\ge 0$。

若答案为 $3$，直接构造。

若答案为 $2$，分两种操作类型相同/不同讨论。

若相同，令两次都为 $2$ 操作，我们需要找到一个区间，满足将这个区间替换成前缀数组后，整个序列的前缀数组均 $\ge 0$。令第一步操作的区间为 $[l,r]$，则 $[1,l-1]$ 的前缀数组需要 $\ge 0$，令 $l=1$，是不劣的，故第一次操作一定是操作一个前缀。枚举这个前缀，需要维护：单点修改，求前缀和数组最小值。用线段树维护前缀和数组，单点修改对应了区间加减，查询对应了全局最小值。

若不同，不妨令第一次为 $3$ 操作，第二次为 $2$ 操作，考虑分治，令当前区间为 $[l,r]$，中点为 $mid$，令 $a_i$ 为原数组，$s_i$ 为前缀和。

对于所有 $i \in [mid+1,r]$ 计算：

• $A_i$：若第一次操作的右端点为 $i$，则操作完后 $a_{mid+1}=A_i$。计算是容易的。
• $B_i$：若右端点为 $i$，第一次操作完之后，$[1,mid]$ 的和至少是多少才能保证对于所有 $j \in [mid+1,n]$，有 $s_j \ge 0$。$B_i$ 由两部分：$[mid+1,r],[r+1,n]$ 确定，$[r+1,n]$ 是容易计算的，预处理原数组中 $s_i$ 的后缀最小值，计算 $[mid+1,r]$ 中后缀和的和即可。$[mid+1,r]$ 有点麻烦，考虑一个位置 $j$，第一次操作完之后，$[mid+1,j]$ 中的和 $t_j$ 会随着 $r$ 的增加发生什么变化：令新加入的数为 $a_r$，则对于所有 $j \in [mid+1,r-1]$，$t_j$ 会增加 $(j-mid)\cdot t_j$。将所有 $j$ 看成一条直线 $y=(j-mid) \cdot x+b$，计算 $B_i$ 可以看做查询凸包上 $x=s_i-s_{mid}$ 处的 $y$ 值。可以用李超树或单调栈维护。

对于所有 $i \in [l,mid]$ 计算：

• $D_i$：原序列中 $[i,m]$ 后缀和之和。
• $E_i$：第一次操作完之后，若左端点为 $i$，则 $a_{mid+1}$ 至少为多少才能保证 $[1,mid]$ 中所有前缀和非负。同样的考虑将 $l$ 减少 $1$ 之后，所有位置 $j$ 的前缀和 $t_j$ 会发生什么变化，这个也可以写成一条直线 $y=(j-i+1)\cdot x+b$，我们需要找到一个最小的 $x$ 使得对于所有直线均有 $y \ge 0$，即 $(j+1)x+b \ge i \cdot x$，可以看做求直线 $y=i \cdot x$ 和凸包的交点，用单调栈+二分维护，如果不介意多个 $\log$ 的话也可以用李超树维护+二分，也能擦着时限过。
• $F_i$：原序列中 $[1,i-1]$ 的和。

一个合法的第一次操作区间 $[L,R]$ 需要满足：

• $[1,L-1]$ 的前缀和数组均 $\ge 0$，很好判断。
• $A_R \ge E_L$
• $D_L+F_L+A_R(mid-L+1) \ge B_R$。

三个限制条件分别令 $[1,L-1],[L,mid],[mid+1,n]$ 三段满足条件。将所有满足第一条限制的 $L$，和所有 $R$ 搞出来，按 $A_R$ 或 $E_L$ 排序。第三个限制，对于所有 $L$ 可以看成直线 $y=(mid-L+1) \cdot x+(D_L+F_L)$，对于所有 $R$ 可以看做查询 $x=A_R$。

复杂度 $O(n \log^2 n)$。

/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int n,dirt;
struct Line
{
	int k,b;
};
struct SegTree
{
	int t[800015],tag[800015];
void pushdown(int id)
{
	if(tag[id])
	{
		t[id<<1]+=tag[id],t[id<<1|1]+=tag[id];
		tag[id<<1]+=tag[id],tag[id<<1|1]+=tag[id];
		tag[id]=0;
	}
}
void update_add(int id,int l,int r,int x,int y,int d)
{
	if(x<=l&&r<=y)
	{
		tag[id]+=d,t[id]+=d;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(id);
	if(x<=mid) update_add(id<<1,l,mid,x,y,d);
	if(y>mid) update_add(id<<1|1,mid+1,r,x,y,d);
	t[id]=min(t[id<<1],t[id<<1|1]);
}
void update(int i,int x,int y,int tp)
{
	if(tp==0)
	{
		update_add(1,1,n,i,n,-x);
		update_add(1,1,n,i,n,y);
	}
	else
	{
		update_add(1,1,n,1,i,-x);
		update_add(1,1,n,1,i,y);
	}
}
}st;
struct Lichao
{
Line p[2000005];
int t[5000005];
int ls[5000005],rs[5000005];
int idx,tid;
void init()
{
	idx=0,tid=1;
	ls[1]=0,rs[1]=0,t[1]=0;
	p[0].k=1,p[0].b=-INF;
}
int add_line(int k,int b)
{
	p[++idx].k=k,p[idx].b=b;
	return idx;
}
int get_y(int id,int x)
{
	return p[id].k*x+p[id].b;
}
void update(int &id,int l,int r,int lid)
{
	if(!id) id=++tid,t[id]=0,ls[id]=rs[id]=0;
	int mid=(l+1000000+r+1000000)/2-1000000;
	if(get_y(lid,mid)>get_y(t[id],mid)) swap(lid,t[id]);
	if(get_y(lid,l)>get_y(t[id],l)) update(ls[id],l,mid,lid);
	if(get_y(lid,r)>get_y(t[id],r)) update(rs[id],mid+1,r,lid);	
}
void insert(int &id,int l,int r,int x,int y,int lid)
{
	if(!id) id=++tid,t[id]=0,ls[id]=rs[id]=0;
	if(x<=l&&r<=y)
	{
		update(id,l,r,lid);
		return;
	}
	int mid=(l+1000000+r+1000000)/2-1000000;
	if(x<=mid) insert(ls[id],l,mid,x,y,lid);
	if(y>mid) insert(rs[id],mid+1,r,x,y,lid);
}
int query(int id,int l,int r,int x)
{
	assert(l<=x&&x<=r);
	if(!id) return -INF;
	int mid=(l+r)/2;
	int res=get_y(t[id],x);
	if(l==r) return res;
	if(x<=mid) res=max(res,query(ls[id],l,mid,x));
	else res=max(res,query(rs[id],mid+1,r,x));
	return res;
}
}lt;
int A[200005];
int a[200005],b[200005],c[200005],d[200005],e[200005],f[200005],ps[200005],ss[200005],pspm[200005],pssm[200005];

vector <pii > stk;
vector <double > pnt;
double get(pii x,pii y)
{
	if(x.fi==y.fi) return (x.se>y.se?-1e18:1e18);
	return 1.0*(y.se-x.se)/(x.fi-y.fi);
}
void ins(pii li)
{
	if(!stk.size()) stk.pb(li),pnt.pb(-1e18);
	else
	{
		while(stk.size()>1&&get(li,stk.back())<pnt.back()) stk.pop_back(),pnt.pop_back();
		pnt.pb(get(li,stk.back())),stk.pb(li);
	}
}
double inter(pii l1,pii l2)
{
	return 1.0*(l2.se-l1.se)/(l1.fi-l2.fi);
}
int query(pii li)
{
	if(!stk.size()) return INF;
	pnt.pb(1e18);
	int L=0,R=pnt.size()-2,res=0;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		double tmp=inter(stk[mid],li);
		if(pnt[mid]<=tmp&&tmp<=pnt[mid+1]) 
		{
			res=mid;
			break;
		}
		if(tmp>pnt[mid+1]) L=mid+1;
		else R=mid-1;
	}
	pnt.pop_back();
	return ceil(inter(stk[res],li));
}


pii divide(int l,int r)
{
	if(l>=r) return mp(-1,-1);
	int mid=(l+r)>>1;
	for(int i=mid+1,s=0;i<=r;i++) s+=A[i],a[i]=s;
	lt.init();
	int rt=1;
	for(int i=mid+1,s=0,sum=0;i<=r;i++)
	{
		s+=(i-mid)*A[i];
		sum+=A[i];
		int K=i-mid,B=s;
		B-=K*sum;
		int lid=lt.add_line(-K,-B);
		lt.insert(rt,-n,n,-n,n,lid);
		b[i]=lt.query(rt,-n,n,sum);
		b[i]=max(b[i],-(pssm[i+1]-ps[i]+s));
	}
	for(int i=mid,s=0,sum=0;i>=l;i--)
	{
		sum+=A[i],s+=sum;
		d[i]=s;
	}
	lt.init();
	
	stk.clear(),pnt.clear();
	for(int i=mid,sum=0,tag=0;i>=l;i--)
	{
		sum+=A[i],tag+=sum;
		int K=(i+1),B=sum-tag;
		ins(mp(-K,-B));
		e[i]=query(mp(-i,tag+ps[i-1]));
	}
	for(int i=mid;i>=l;i--) f[i]=ps[i-1];
	vector <array<int,4> > vec;
	vec.clear();
	for(int i=l;i<=mid;i++) if(pspm[i-1]>=0) vec.pb({e[i],0,i});
	for(int i=mid+1;i<=r;i++) vec.pb({a[i],1,i});
	sort(vec.begin(),vec.end());
	lt.init();
	for(int i=0;i<vec.size();i++)
	{
		int u=vec[i][2];
		if(vec[i][1]==0) 
		{
			int K=mid-u+1,B=d[u]+f[u];
			int lid=lt.add_line(K,B);
			lt.insert(rt,-n,n,-n,n,lid);
		}
		else
		{
			int tmp=lt.query(rt,-n,n,a[u]);
			if(tmp>=b[u])
			{
				int v=-1;
				for(int j=0;j<i;j++) if(vec[j][1]==0)
				{
					v=vec[j][2];
					int K=mid-v+1,B=d[v]+f[v];
					if(K*a[u]+B==tmp) break;
				}
				assert(v!=-1);
				return mp(v,u);
			}
		}
	}
	
	pii tmp=divide(l,mid);
	if(tmp.fi!=-1) return tmp;
	tmp=divide(mid+1,r);
	if(tmp.fi!=-1) return tmp;
	return mp(-1,-1);
}
vector <array<int,3> > chk()
{
	memset(st.t,0,sizeof(st.t));
	memset(st.tag,0,sizeof(st.tag));
	for(int i=1;i<=n;i++) st.update(i,0,A[i],0);
	for(int i=1,s=0;i<=n;i++)
	{
		s+=A[i];
		st.update(i,A[i],s,0);
		if(st.t[1]>=0)
		{
			vector <array<int,3> > vec;
			vec.pb({2,1,i});
			vec.pb({2,1,n});
			return vec;
		}
	}
	
	memset(st.t,0,sizeof(st.t));
	memset(st.tag,0,sizeof(st.tag));
	for(int i=1;i<=n;i++) st.update(i,0,A[i],1);
	for(int i=n,s=0;i>=1;i--)
	{
		s+=A[i];
		st.update(i,A[i],s,1);
		if(st.t[1]>=0)
		{
			vector <array<int,3> > vec;
			vec.pb({3,i,n});
			vec.pb({3,1,n});
			return vec;
		}
	}
	
	memset(pssm,0x3f,sizeof(pssm)),memset(pspm,0x3f,sizeof(pspm));
	for(int i=1;i<=n;i++) ps[i]=ps[i-1]+A[i],pspm[i]=pssm[i]=ps[i];
	for(int i=1;i<=n;i++) ss[i]=ss[i+1]+A[i];
	for(int i=2;i<=n;i++) pspm[i]=min(pspm[i-1],pspm[i]);
	for(int i=n-1;i>=1;i--) pssm[i]=min(pssm[i+1],pssm[i]);
	pii tmp=divide(1,n);
	vector <array<int,3> > vec;
	for(int i=0;i<100;i++) vec.pb({-1,-1,-1});
	if(tmp.fi==-1) return vec;
	vec.clear();
	vec.pb({3,tmp.fi,tmp.se}),vec.pb({2,1,n});
	return vec;
}
void solve()
{
	cin>>n>>dirt;
	for(int i=1;i<=n;i++) cin>>A[i];
	bool ok=1;
	for(int i=1;i<=n;i++) ok&=(A[i]>=0);
	if(ok) 
	{
		cout<<"0\n";
		return;
	}
	ok=1;
	for(int i=1,s=0;i<=n;i++) s+=A[i],ok&=(s>=0);
	if(ok)
	{
		cout<<"1\n";
		cout<<2<<" "<<1<<" "<<n<<"\n";
		return;
	}
	ok=1;
	for(int i=n,s=0;i>=1;i--) s+=A[i],ok&=(s>=0);
	if(ok)
	{
		cout<<"1\n";
		cout<<3<<" "<<1<<" "<<n<<"\n";
		return;
	}
	
	for(int i=1;i<=n;i++) A[i]*=-1;
	ok=1;
	for(int i=1;i<=n;i++) ok&=(A[i]>=0);
	if(ok) 
	{
		cout<<"1\n1\n";
		return;
	}
	ok=1;
	for(int i=1,s=0;i<=n;i++) s+=A[i],ok&=(s>=0);
	if(ok)
	{
		cout<<"2\n1\n";
		cout<<2<<" "<<1<<" "<<n<<"\n";
		return;
	}
	ok=1;
	for(int i=n,s=0;i>=1;i--) s+=A[i],ok&=(s>=0);
	if(ok)
	{
		cout<<"2\n1\n";
		cout<<3<<" "<<1<<" "<<n<<"\n";
		return;
	}
	for(int i=1;i<=n;i++) A[i]*=-1;
	vector <array<int,3> > v1=chk();
	reverse(A+1,A+1+n);
	vector <array<int,3> > v2=chk();
	for(int i=0;i<v2.size();i++) 
	{
		if(v2[i][0]==2) v2[i][0]=3;
		else if(v2[i][0]==3) v2[i][0]=2;
		v2[i][1]=n-v2[i][1]+1,v2[i][2]=n-v2[i][2]+1;
		swap(v2[i][1],v2[i][2]);
	}
	reverse(A+1,A+1+n);
	for(int i=1;i<=n;i++) A[i]*=-1;
	vector <array<int,3> > v3=chk();
	v3.insert(v3.begin(),{1,-1,-1});
	reverse(A+1,A+1+n);
	vector <array<int,3> > v4=chk();
	v4.insert(v4.begin(),{1,-1,-1});
	for(int i=0;i<v4.size();i++) 
	{
		if(v4[i][0]==2) v4[i][0]=3;
		else if(v4[i][0]==3) v4[i][0]=2;
		v4[i][1]=n-v4[i][1]+1,v4[i][2]=n-v4[i][2]+1;
		swap(v4[i][1],v4[i][2]);
	}
	vector <array<int,3> > ans;
	for(int i=0;i<100;i++) ans.pb({-1,-1,-1});
	if(v1.size()<ans.size()) ans=v1;
	if(v2.size()<ans.size()) ans=v2;
	if(v3.size()<ans.size()) ans=v3;
	if(v4.size()<ans.size()) ans=v4;
	cout<<ans.size()<<"\n";
	for(int i=0;i<ans.size();i++) 
	{
		cout<<ans[i][0];
		if(ans[i][0]!=1) cout<<" "<<ans[i][1]<<" "<<ans[i][2];
		cout<<"\n";
	}
}
signed main()
{
	freopen("presuffix.in","r",stdin);
	freopen("presuffix.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
}