什么方法?

做完了,数组大了一些,秒杀,可是我不知道这是什么算法,哪位神牛告诉我?

受某牛“括号法”启发,存左括号和右括号的个数,加个查询。

program vijos1448;

var

n,m,i:longint;

k,x1,x2:longint;

t:array[1..2,1..200010]of longint;

procedure add(now,x:longint);

var

q,w,m:longint;

p:longint;

begin

q:=1; w:=n;

p:=1;

while q=x then w:=m

else begin

q:=m+1;

inc(p);

end;

end;

inc(t[now,p]);

end;

procedure see(y,x:longint);

var

q,w,p:longint;

ans:longint;

begin

ans:=0;

q:=1; w:=n;

p:=1;

while q=x then w:=m

else begin

q:=m+1;

inc(ans,t[1,p]);

inc(p);

end;

end;

inc(ans,t[1,p]);

q:=1; w:=n;

p:=1;

while q=y then w:=m

else begin

q:=m+1;

dec(ans,t[2,p]);

inc(p);

end;

end;

writeln(ans);

end;

begin

readln(n,m);

for i:=1 to m do begin

readln(k,x1,x2);

if k=1 then begin

add(1,x1);

add(2,x2);

end

else see(x1,x2);

end;

end.

2 条评论

  • 1

信息

ID
1448
难度
6
分类
数据结构 | 线段树 点击显示
标签
递交数
2916
已通过
872
通过率
30%
被复制
6
上传者