题意：
给出一个 (k imes k) 的网格和 (n) 次操作。其中 (k) 为奇数。
每次操作给出一个数 (m)。每次你要找出一个三元组 ((x,l,r)) 使得：
- (r-l+1=m)
- ((x,l),(x,l+1),(x,l+2),dots,(x,r)) 都未被访问过。
- (sumlimits_{i=l}^r|x-frac{k+1}{2}|+|y-frac{k+1}{2}|) 最小。换句话说，((x,l),(x,l+1),(x,l+2),dots,(x,r)) 到网格正中心的距离之和最小
- 在满足 1,2,3 的条件下，若有多个三元组，选择 (x) 最小的，若还有多种，选择 (l) 最小的。
求出 ((x,l,r)) 之后，你会将 ((x,l),(x,l+1),(x,l+2),dots,(x,r)) 都设为访问过。
(k in [1,300001])。
神仙题 %%%%%（看调试语句就知道我这道题调了多久了）
我们记 (mid=frac{k+1}{2})
首先有一个显而易见的性质：对于那些没有位置被选择的行，只有最接近 (mid) 的两行才会被选。
也就是说，有位置被选择的行一定会组成一个区间。
我们对这两行进行特判。假设目前有位置被选择的行组成的区间为 ((cl,cr))，那么选择第 (cl) 行的最小代价为 (|mid-cl| imes m+sumlimits_{i=1}^{lfloorfrac{m}{2}
floor}i+sumlimits_{i=1}^{lfloorfrac{m-1}{2}
floor}i)，第 (cr) 行的代价也同理。
如果我们选择一个有位置被选择的行，那么显然这一行最中心的位置被选择了。
我们将这一行一分为二，分为左右两部分。这里以左半部分为例，右半部分也同理。
假设第 (i) 行左半部分最右边的空位为 (x)，如果 (x<m) 就不能选择这一行。
如果 (xgeq m)，那么可以选择这一行，并且代价最小的区间一定是 ((x-m+1,x))，考虑如何计算这一行的代价。
我们将这个长度为 (m) 的区间的右端点与 ((mid,mid)) 对齐，此时代价为 (frac{m(m-1)}{2})。
然后从 ((mid,mid)) 移动到 ((i,x))，不难发现每移一步代价增加 (m)，即 (m imes (|i-mid|+|x-mid|)+frac{m(m-1)}{2})。
由于 (m) 是一个确定的值，代价最小就意味着 ((|i-mid|+|x-mid|))。
我们建立一个结构体 (data)，里面存三个值 (v,x,l)，并重载小于号使其与上面的比较方式相吻合。
维护一棵线段树，线段树上的节点存该子树中最小的 (data)。叶子节点为 (data) 的大根堆。
线段树的下标表示 (x)，也就是第 (i) 行左半部分最右侧的空位的位置。
我们要查询 ([m,mid]) 中最小的三元组，就在 ([m,mid]) 对应的区间中查找。
如果我们选择一个区间 ((x,l,r))，就从线段树中删除 ((|mid-x|+|mid-r|,x,r)) 并加入 ((|mid-x|+|mid-l+1|,x,l-1)) 即可。
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a) a.begin(),a.end()
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,0x3f,sizeof(a))
#define y1 y1010101010101
#define y0 y0101010101010
typedef pair<int,int> pii;
typedef long long ll;
int n,k,mid;
struct data{
ll v;int x,l;
data(ll _v=0,int _x=0,int _l=0){
v=_v;x=_x;l=_l;
}
friend bool operator <(data a,data b){
if(a.v^b.v) return a.v<b.v;
if(a.x^b.x) return a.x<b.x;
return a.l<b.l;
}
friend bool operator >(data a,data b){
return b<a;
}
friend bool operator ==(data a,data b){
return (a.v==b.v&&a.x==b.x&&a.l==b.l);
}
};
const data INF=data(0x3f3f3f3f3f3f3f3fll,0x3f3f3f3f,0x3f3f3f3f);
struct segtree{
struct node{
int l,r;
data mn;
} s[300005<<2];
priority_queue<data,vector<data>,greater<data> > pq[300005];
inline void build(int k,int l,int r){
s[k].l=l;s[k].r=r;s[k].mn=INF;if(l==r) return;
int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
inline void modify(int k,int ind,data p){
// printf("%d
",k);
// if(!ind) return;
if(s[k].l==s[k].r){
// printf("%d
",s[k].l);
pq[s[k].l].push(p);
s[k].mn=pq[s[k].l].top();
return;
}
int mid=(s[k].l+s[k].r)>>1;
if(ind<=mid) modify(k<<1,ind,p);
else modify(k<<1|1,ind,p);
s[k].mn=min(s[k<<1].mn,s[k<<1|1].mn);
}
inline void del(int k,int ind){
if(!ind) return;
// printf("%d
",k);
if(s[k].l==s[k].r){
// printf("%d
",s[k].l);
// data xx=pq[s[k].l].top();
// printf("delete %d %d %d
",xx.v,xx.x,xx.l);
// assert(!pq[s[k].l].empty());
pq[s[k].l].pop();
if(pq[s[k].l].empty()) s[k].mn=INF;
else s[k].mn=pq[s[k].l].top();
return;
}
int mid=(s[k].l+s[k].r)>>1;
if(ind<=mid) del(k<<1,ind);
else del(k<<1|1,ind);
s[k].mn=min(s[k<<1].mn,s[k<<1|1].mn);
}
inline data query(int k,int l,int r){
// printf("%d
",k);
if(l>r) return INF;
if(l<=s[k].l&&s[k].r<=r) return s[k].mn;
int mid=(s[k].l+s[k].r)>>1;
if(r<=mid) return query(k<<1,l,r);
else if(l>mid) return query(k<<1|1,l,r);
else return min(query(k<<1,l,mid),query(k<<1|1,mid+1,r));
}
} L,R;
int main(){
scanf("%d%d",&n,&k);mid=(k+1)>>1;
int cl=mid,cr=mid;L.build(1,0,mid);R.build(1,0,mid);
for(int i=1;i<=n;i++){
int m;scanf("%d",&m);
data ansp=INF;
ll v=1ll*(m/2)*((m/2)+1)/2+1ll*((m-1)/2)*((m-1)/2+1)/2;
if(cl!=0) ansp=min(ansp,data(v+1ll*m*abs(mid-cl),cl,mid-m/2));
if(cr!=k+1) ansp=min(ansp,data(v+1ll*m*abs(mid-cr),cr,mid-m/2));
data x=L.query(1,m,mid),y=R.query(1,m,mid);x.l-=m-1;
// printf("%lld %d %d
",x.v,x.x,x.l);
// printf("%lld %d %d
",y.v,y.x,y.l);
if(x.v!=0x3f3f3f3f3f3f3f3fll) x.v=x.v*m+1ll*m*(m-1)/2;
if(y.v!=0x3f3f3f3f3f3f3f3fll) y.v=y.v*m+1ll*m*(m-1)/2;
ansp=min(ansp,x);ansp=min(ansp,y);
if(ansp.v==0x3f3f3f3f3f3f3f3fll){puts("-1");continue;}
// printf("%lld %d %d
",x.v,x.x,x.l);
// printf("%lld %d %d
",y.v,y.x,y.l);
printf("%d %d %d
",ansp.x,ansp.l,ansp.l+m-1);
if(ansp.x==cl){
L.modify(1,ansp.l-1,data(abs(cl-mid)+abs(ansp.l-1-mid),cl,ansp.l-1));
// printf("L %d %d %d %d
",ansp.l-1,abs(cl-mid)+abs(ansp.l-1-mid),cl,ansp.l-1);
R.modify(1,k-ansp.l-m+1,data(abs(cl-mid)+abs(ansp.l+m-mid),cl,ansp.l+m));
// printf("R %d %d %d %d
",k-ansp.l-m+1,abs(cl-mid)+abs(ansp.l+m-mid),cl,ansp.l+m);
if(cl==cr) cr++;cl--;
continue;
}
else if(ansp.x==cr){
L.modify(1,ansp.l-1,data(abs(cr-mid)+abs(ansp.l-1-mid),cr,ansp.l-1));
// printf("L %d %d %d %d
",ansp.l-1,abs(cr-mid)+abs(ansp.l-1-mid),cr,ansp.l-1);
R.modify(1,k-ansp.l-m+1,data(abs(cr-mid)+abs(ansp.l+m-mid),cr,ansp.l+m));
// printf("R %d %d %d %d
",k-ansp.l-m+1,abs(cr-mid)+abs(ansp.l+m-mid),cr,ansp.l+m);
cr++;
continue;
// continue;
}
else if(ansp==x){
L.del(1,ansp.l+m-1);
// printf("delL %d
",ansp.l+m-1);
L.modify(1,ansp.l-1,data(abs(ansp.x-mid)+abs(ansp.l-1-mid),ansp.x,ansp.l-1));
// printf("L %d %d %d %d
",ansp.l-1,abs(ansp.x-mid)+abs(ansp.l-1-mid),ansp.x,ansp.l-1);
// continue;
}
else if(ansp==y){
R.del(1,k-ansp.l+1);
// printf("delR %d
",k-ansp.l+1);
R.modify(1,k-(ansp.l+m)+1,data(abs(ansp.x-mid)+abs(ansp.l+m-mid),ansp.x,ansp.l+m));
// printf("R %d %d %d %d
",k-(ansp.l+m)+1,abs(ansp.x-mid)+abs(ansp.l+m-mid),ansp.x,ansp.l+m);
// continue;
}
}
return 0;
}