俄罗斯方块 tetris
【题意】
俄罗斯方块游戏，在一个宽度为n高度为h的矩阵中进行，给定初始状态，每次给定一个形状的方块，将它放到最靠左进行最少旋转次数可不出现“洞”（就是说同一列方块之间有缝隙）且加入后最高高度不超过h的位置，并输出这个位置，跟一般的俄罗斯方块一样，一行满了便会消行
各种编号对应的方块
0
**
*
*
1
**
*
*
2
**
**
3
**
**
4
***
*
5
**
**
6
****
【输入】
第一行n、m、h（皆小于等于100000）
接下来m行每行一个数字表示加入的方块的形状
【输出】
对于每次加入输出其位置
十分麻烦的题
首先需要一个函数（这里是could）来判断某位置是否能放入一个某形状的方块
然后用线段树来维护，维护两个值，区间内高度最低值和用一个7位2进制数表示的以区间内的点为起点每种形状是否能放入
那么对于每次插入，查询最靠左的点，并更新有关的最多七个点，总查询并更新复杂度为mlogn
对于消行，每次重建线段树即可，消行次数最多为4*m/n，每次重建为nlogn，所以总重建复杂度为mlogn
虽然常数比较大，但这个复杂度对于时限3s的本题还是很轻松的
program tetris;
const
plus:array [0..6,1..4,0..3] of longint
=(
((3,1,0,0),(1,1,2,0),(1,3,0,0),(2,1,1,0)),
((1,3,0,0),(1,1,2,0),(3,1,0,0),(2,1,1,0)),
((1,2,1,0),(2,2,0,0),(0,0,0,0),(0,0,0,0)),
((1,2,1,0),(2,2,0,0),(0,0,0,0),(0,0,0,0)),
((1,2,1,0),(1,3,0,0),(1,2,1,0),(3,1,0,0)),
((2,2,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0)),
((1,1,1,1),(4,0,0,0),(0,0,0,0),(0,0,0,0))
);
dif:array [0..6] of longint=(4,4,2,2,4,1,2);
long:array [0..6,1..4] of longint
=(
(2, 3, 2, 3 ),
(2, 3, 2, 3 ),
(3, 2, 0, 0 ),
(3, 2, 0, 0 ),
(3, 2, 3, 2 ),
(2, 0, 0, 0 ),
(4, 1, 0, 0 )
);
need:array [0..6,1..4,0..2] of longint
=(
((-2,9,9), (0,1,9), (0,9,9), (0,0,9) ),
((2,9,9), (0,0,9), (0,9,9), (-1,0,9) ),
((0,-1,9), (1,9,9), (9,9,9), (9,9,9) ),
((1,0,9), (-1,9,9), (9,9,9), (9,9,9) ),
((1,-1,9), (1,9,9), (0,0,9), (-1,9,9) ),
((0,9,9), (9,9,9), (9,9,9), (9,9,9) ),
((0,0,0), (9,9,9), (9,9,9), (9,9,9) )
);
var
minn,tot,h,n,m,i,j,k,t:longint;
high:array [0..100001] of longint;
min,left,right,status:array [0..200001] of longint;
function could (now,form:longint):longint;
var
ok:boolean;
i,j,k:longint;
begin
for i:=1 to dif[form] do
begin
if (high[now]+plus[form,i,0]>h)or(now+long[form,i]-1>n) then continue;
ok:=true;
for j:=0 to long[form,i]-2 do
if (high[now+j]-high[now+j+1]<>need[form,i,j])
or(high[now+j+1]+plus[form,i,j+1]>h)
then
begin
ok:=false;
break
end;
if ok then exit(i);
end;
exit(0);
end;
procedure change (who,l,r,now:longint);
var
i:longint;
begin
if l=r then
begin
min[now]:=high[who];
status[now]:=0;
for i:=0 to 6 do
if could(who,i)<>0 then status[now]:=status[now] or (1 shl i);
exit;
end;
if who<=(l+r) div 2 then change(who,l,(l+r) div 2,left[now])
else change(who,(l+r) div 2+1,r,right[now]);
status[now]:=status[left[now]] or status[right[now]];
if min[left[now]]<min[right[now]] then min[now]:=min[left[now]]
else min[now]:=min[right[now]];
end;
procedure quick (s,e,now:longint);
var
i,mid:longint;
begin
if s=e then
begin
left[now]:=0;
right[now]:=0;
status[now]:=0;
min[now]:=high[s];
for i:=0 to 6 do
if could(s,i)<>0 then status[now]:=status[now] or (1 shl i);
exit;
end;
mid:=(s+e) div 2;
inc(tot);
left[now]:=tot;
inc(tot);
right[now]:=tot;
quick(s,mid,left[now]);
quick(mid+1,e,right[now]);
status[now]:=status[left[now]] or status[right[now]];
if min[left[now]]<min[right[now]] then min[now]:=min[left[now]]
else min[now]:=min[right[now]];
end;
procedure build ;
begin
tot:=0;
quick(1,n,0);
end;
function find (form,l,r,now:longint):longint;inline;
begin
if l=r then exit(l);
if status[left[now]] or (1 shl form)=status[left[now]] then
exit(find(form,l,(l+r) div 2,left[now]))
else
exit(find(form,(l+r) div 2+1,r,right[now]));
end;
procedure update (now,form,status:longint);
var
i,k:longint;
begin
for i:=0 to long[form,status]-1 do
high[now+i]:=high[now+i]+plus[form,status,i];
for i:=0 to long[form,status]-1 do
change(now+i,1,n,0);
for i:=1 to 3 do
if now-i>0 then
change(now-i,1,n,0);
if min[0]<>0 then
begin
for i:=1 to n do
high[i]:=high[i]-min[0];
build;
end;
end;
begin
assign(input,'tetris.in');
reset(input);
assign(output,'tetris.out');
rewrite(output);
read(n,m,h);
minn:=maxlongint;
for i:=1 to n do
begin
read(high[i]);
if high[i]<minn then minn:=high[i];
end;
for i:=1 to n do
high[i]:=high[i]-minn;
build;
for i:=1 to m do
begin
read(t);
j:=find(t,1,n,0);
writeln(j-1);
k:=could(j,t);
update(j,t,k);
end;
close(input);
close(output);
end.