线段树过了，看楼下各种朴素过，顿时蛋疼。。。。

既然没人写线段树题解，我就写一个

用线段树 f 维护，每个点 i 向左、向右最长连续空闲区域能延伸到哪里：l[i]、r[i]，将一段内容全部修改传个标记就可以了

同时记 g[i] 为以 i 开始的最长空闲区域长度，其中 i-1 不空闲，即 i ~ i+g[i]-1 这段空闲区域是极大的，用线段树维护区间 g 的最大值

malloc(K)：

找出最早出现的能容纳 K 个的区域。这时在线段树 g 中跑一下，如果左子树最大值 >=K 就往左子树走，否则往右子树走，这样就能找到最早出现的位置 i 了

然后就是在线段树 f 中将 i+K ~ r[i] 这段的 l 全部改成 i+K，将 i ~ i+K-1 这段全部抹掉

同时将线段树 g 中的 g[i] 删除，插入 g

free(i,K)：

插入 i ~ i+K-1 后，左边空闲区域和右边空闲区域会合并，因此找出最左端 l 和最右端 r

在线段树 f 中将 l ~ r 这段 l 全部改成 l ，r 全部改成 r

在线段树 g 中将 g[ l ] 更新，删除 g

print：

这个随便map或者哈希搞一下就好了

此题是深坑啊。数据坑爹啊。

首先，暴力就别想了。我写了三个版本的暴力，最长的足足130行，依旧过不了。

所以只能线段树了。思路很简单，不会的可以看看 vijos 1620小白逛公园 ，以及 POJ 3667，就应该没什么问题了。

剩下处理的问题主要是记录变量名对应的值。感谢 Sprite_210 的提示，说变量名全小于四位，所以 string->int 的映射很简单，转成26进制数即可。每次 malloc 完后往映射表中加入一个 string -> <int, int>的映射，记录被分配到的内存区间。free 时把区间调出来，在线段树中删除，再把该映射删除即可。其实这道题如果加强一下，把变量名的字符集拓展到 ASCII，那么就颇有难度，还得加上平衡树之类的了，不下200行应该写不完。

然后是忠告：能加判断的地方都给加上判断。数据中貌似有很多一个变量名重复申请多次内存的情况。这种情况下，**原内存不释放，但变量的值会变成新的内存地址；如果空间不足，则变量值变为0**。我以为这种情况直接忽略，结果总是20分...

type
node=record
l,r,m,llen,maxlen,rlen:longint;
end;

var
a:array[0..300001] of node;
b:array[1..100000] of string;
c,num,order,leng,ll,rr:array[0..100001] of longint;
n,i,s,j:longint;
st:string;
code:integer;

procedure sort(l,r:longint);
var
i,j,y:longint;
x,yy:string;
begin
i:=l; j:=r; x:=b[(l+r) div 2];
repeat
while b[i]<x do inc(i);
while x<b[j] do dec(j);
if not(i>j) then
begin
y:=num[i]; num[i]:=num[j]; num[j]:=y;
y:=order[i]; order[i]:=order[j]; order[j]:=y;
y:=leng[i]; leng[i]:=leng[j]; leng[j]:=y;
yy:=b[i]; b[i]:=b[j]; b[j]:=yy;
inc(i); dec(j);
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;

procedure sort1(l,r:longint);
var
i,j,y,x:longint;
begin
i:=l; j:=r; x:=num[(l+r) div 2];
repeat
while num[i]<x do inc(i);
while x<num[j] do dec(j);
if not(i>j) then
begin
y:=num[i]; num[i]:=num[j]; num[j]:=y;
y:=order[i]; order[i]:=order[j]; order[j]:=y;
y:=leng[i]; leng[i]:=leng[j]; leng[j]:=y;
y:=c[i]; c[i]:=c[j]; c[j]:=y;
inc(i); dec(j);
end;
until i>j;
if l<j then
sort1(l,j);
if i<r then
sort1(i,r);
end;

procedure build(k,left,right:longint);
begin
a[k].l:=left; a[k].r:=right; a[k].m:=(left+right) div 2;
a[k].llen:=right-left+1; a[k].rlen:=a[k].llen; a[k].maxlen:=a[k].rlen;
if left=right then exit;
build(k shl 1,left,a[k].m); build(k shl 1+1,a[k].m+1,right);
end;

function max(t1,t2:longint):longint;
begin
if t1>t2 then max:=t1 else max:=t2;
end;

function find(k,len:longint):longint;
begin
if a[k].llen>=len then exit(a[k].l);
if a[k shl 1].maxlen>=len then exit(find(k shl 1,len));
if a[k shl 1].rlen+a[k shl 1+1].llen>=len then exit(a[k shl 1].r-a[k shl 1].rlen+1);
if a[k shl 1+1].maxlen>=len then exit(find(k shl 1+1,len));
end;

procedure change(k,left,right:longint);
begin
if (a[k].l=left) and (a[k].r=right)
then begin a[k].llen:=0; a[k].rlen:=0; a[k].maxlen:=0; exit; end;
if left>a[k].m then change(k shl 1+1,left,right) else
if right<=a[k].m then change(k shl 1,left,right) else
begin change(k shl 1,left,a[k].m); change(k shl 1+1,a[k].m+1,right); end;
if a[k shl 1].llen=a[k].m-a[k].l+1
then a[k].llen:=a[k shl 1].llen+a[k shl 1+1].llen
else a[k].llen:=a[k shl 1].llen;
if a[k shl 1+1].rlen=a[k].r-a[k].m
then a[k].rlen:=a[k shl 1+1].rlen+a[k shl 1].rlen
else a[k].rlen:=a[k shl 1+1].rlen;
a[k].maxlen:=max(max(a[k shl 1].maxlen,a[k shl 1+1].maxlen),a[k shl 1].rlen+a[k shl 1+1].llen);
end;

procedure change1(k,left,right:longint);
begin
if (a[k].l=left) and (a[k].r=right)
then begin a[k].llen:=right-left+1; a[k].rlen:=a[k].llen; a[k].maxlen:=a[k].llen; exit; end;
if left>a[k].m then change1(k shl 1+1,left,right) else
if right<=a[k].m then change1(k shl 1,left,right) else
begin change1(k shl 1,left,a[k].m); change1(k shl 1+1,a[k].m+1,right); end;
if a[k shl 1].llen=a[k].m-a[k].l+1
then a[k].llen:=a[k shl 1].llen+a[k shl 1+1].llen
else a[k].llen:=a[k shl 1].llen;
if a[k shl 1+1].rlen=a[k].r-a[k].m
then a[k].rlen:=a[k shl 1+1].rlen+a[k shl 1].rlen
else a[k].rlen:=a[k shl 1+1].rlen;
a[k].maxlen:=max(max(a[k shl 1].maxlen,a[k shl 1+1].maxlen),a[k shl 1].rlen+a[k shl 1+1].llen);
end;

begin
readln(n);
for i:=1 to n do
begin
readln(st);
delete(st,length(st)-1,2);
if st[length(st)] in ['0'..'9']
then
begin
order[i]:=1; j:=length(st);
while st[j-1]<>'(' do dec(j);
val(copy(st,j,length(st)-j+1),leng[i],code);
b[i]:=copy(st,1,j-9);
end
else
if st[1]='p'
then
begin
order[i]:=3; b[i]:=copy(st,7,length(st)-6);
end
else
begin
order[i]:=2; b[i]:=copy(st,6,length(st)-5);
end;
num[i]:=i;
end;

sort(1,n);
s:=1; c[1]:=1;
for i:=2 to n do
if b[i]=b[i-1]
then c[i]:=s
else begin inc(s); c[i]:=s; end;
sort1(1,n);

build(1,1,100000);
for i:=1 to s do ll[i]:=0;
for i:=1 to n do
case order[i] of
1:begin
if a[1].maxlen<leng[i] then begin ll[c[i]]:=0; continue; end;
ll[c[i]]:=find(1,leng[i]); rr[c[i]]:=ll[c[i]]+leng[i]-1;
change(1,ll[c[i]],rr[c[i]]);
end;
2:if ll[c[i]]>0
then
begin
change1(1,ll[c[i]],rr[c[i]]); ll[c[i]]:=0;
end;
3:writeln(ll[c[i]]);
end;
end.

这题就是朴素的N^2暴力，但是要注意的是N

彻底绝望了，用一个貌似对的树状数组O(n*lognlogn)，调了三个晚上，每条一个晚上多对几个点,最后对了7个点，看见楼上大牛的提示，改成朴素算法，不但速度快了很多，简单AC

这天下：朴素才是王道

哈哈，有时候数组+N^2的算法才是王道!

总算是AC了。。。

别人告诉我说第一个通过的那个人被锁定了而且他的最后登录时间在这个题目发表以前。所以还是有点小小的成就感拉。（别打我。。。我要不是数学好点，OI很菜的。）

大家没过看样子是中钩子了。。。还好我用的链表，通过几次数据存取错误发现几个很重要的所谓的钩子(不能确定，但按我的程序只能这样解释)：

1.有free(var)在malloc(var)之前；

2.有print(var)在malloc(var)之前；

3.(别个告诉我的，也是我主动问的)所有的var都是4位且只有小写字母.(对我来说很重要的一点，看对大家有什么启发没)；

3/8(37%) 　 首页 站务 公告　|　题库/分类/原题 记录 比赛 团队 讨论 |　U-S 搜索 换肤 正體　|　登出

公告 News >> 　　New! 关于给予原管理员 car 封号处理的公告 (2010-4-9 10:04:37) 　　New! Vijos需要你的帮助 (2010-4-6 23:48:32) 　　New! 【请关注】Vijos 创始人『刘康』希望与你结识为朋友~(@^_^@)~ (2010-3-29 17:46:34) 　　Vijos试运行公告 (2010-2-27 14:19:18) 　　CSAPC 开放邮箱提交通道 (2009-11-14 21:11:37)

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--

跳转 Goto >> 　第 1 2 3 4 5 6 7 8 页　添加题目　评测记录　分类筛选 快速转入:题号 模拟 动态规划 字符串处理 搜索 数论 / 数值 计算几何 图结构 树结构

匹配 并查集 贪心 最短路 博弈论 高级数据结构 网络流 其它

Flag 题号 标题 通过 提交 通过率 难度

P1001

谁拿了最多奖学金 10875人 30714次 35% 1

P1002

过河 4526人 22906次 20% 3

P1003

等价表达式 1623人 6776次 24% 2

P1004

伊甸园日历游戏 1489人 4972次 30% 2

P1005

超长数字串 363人 3709次 10% 3

P1006

晴天小猪历险记之Hill 2565人 12548次 20% 2

P1007

绕钉子的长绳子 7213人 18157次 40% 1

P1008

篝火晚会 1843人 5138次 36% 3

P1009

清帝之惑之康熙 732人 5945次 12% 2

P1010

清帝之惑之乾隆 641人 2401次 27% 2

P1011

清帝之惑之顺治 3692人 15995次 23% 2

P1012

清帝之惑之雍正 952人 5085次 19% 3

P1013

强墙 662人 1803次 37% 2

P1014

旅行商简化版 1228人 3934次 31% 2

P1015

十字绣 261人 1546次 17% 2

P1016

北京2008的挂钟 2106人 5844次 36% 3

P1017

划分 127人 563次 23% 2

P1018

智破连环阵 129人 756次 17% 5

P1019

补丁VS错误 657人 2779次 24% 3

P1020

切蛋糕 369人 2161次 17% 4

P1021

Victoria的舞会1 4354人 8266次 53% 2

P1022

Victoria的舞会2 2913人 5244次 56% 2

P1023

Victoria的舞会3 2862人 4794次 60% 3

P1024

卡布列克圆舞曲 2857人 12952次 22% 1

Accepted P1025

小飞侠的游园方案 MySol. 5336人 12248次 44% 2

P1026

毒药？解药？ 1296人 4573次 28% 2

P1027

休息中的小呆 504人 2621次 19% 2

P1028

魔族密码 2988人 7203次 41% 2

P1029

晴天小猪历险记之Number 479人 1799次 27% 2

P1030

重叠的方框 541人 1603次 34% 2

P1031

奶牛加密术 322人 2304次 14% 4

P1032

循环 922人 3814次 24% 2

P1033

整数分解(版本2) 2589人 7345次 35% 2

P1034

家族 4282人 10613次 40% 2

P1035

贪婪的送礼者 5394人 9723次 55% 1

P1036

安装服务器 469人 1501次 31% 2

P1037

搭建双塔 3035人 11951次 25% 2

P1038

添加括号 954人 2561次 37% 2

P1039

最小差距 787人 3944次 20% 2

P1040

高精度乘法 3246人 20077次 16% 3

P1041

神风堂人数 5357人 20623次 26% 1

P1042

捕风捉影 1845人 6921次 27% 1

P1044

Wappo 111人 550次 20% 4

P1045

Kerry 的电缆网络 1422人 7850次 18% 3

P1046

观光旅游 930人 3292次 28% 3

P1047

最小公倍数 438人 5356次 8% 2

P1048

送给圣诞夜的贺卡 549人 3682次 15% 3

P1049

送给圣诞夜的礼品 381人 1335次 29% 2

P1050

送给圣诞夜的行程 89人 661次 13% 4

P1051

送给圣诞夜的极光 3721人 10281次 36% 1

P1052

贾老二算算术 591人 2604次 23% 2

P1053

Easy sssp 485人 6304次 8% 3

P1054

牛场围栏 184人 810次 23% 3

P1055

奶牛浴场 486人 1779次 27% 3

P1056

图形面积 481人 2268次 21% 3

P1057

盖房子 4831人 10204次 47% 2

P1058

粘贴文本 737人 1909次 39% 2

P1059

积木城堡 3662人 13621次 27% 1

P1060

盒子 1209人 3181次 38% 2

P1061

迎春舞会之三人组舞 1816人 4741次 38% 3

P1062

迎春舞会之交谊舞 2113人 5329次 40% 1

P1063

迎春舞会之集体舞 1513人 6478次 23% 2

P1064

迎春舞会之数字舞蹈 1749人 4792次 36% 1

P1065

最小数字倍数 319人 1792次 18% 2

P1066

弱弱的战壕 2582人 4745次 54% 2

P1067

Warcraft III 守望者的烦恼 480人 1806次 27% 3

P1068

新年趣事之玩具 424人 858次 49% 2

P1069

新年趣事之红包 1642人 4548次 36% 2

P1070

新年趣事之游戏 646人 3990次 16% 3

P1071

新年趣事之打牌 1880人 8621次 22% 2

P1072

新年趣事之债务 5340人 7741次 69% 1

P1073

4-Hanoi-Tower 2131人 4996次 43% 2

P1076

海战 1096人 2853次 38% 2

P1077

克隆龙 379人 1174次 32% 3

P1078

松鼠吃果子 3723人 7949次 47% 1

P1079

中青局 383人 1200次 32% 3

P1080

Function(Function(F... 1761人 6985次 25% 2

P1081

野生动物园 267人 3717次 7% 4

P1082

丛林探险 365人 1877次 19% 2

P1083

小白逛公园 276人 2769次 10% 4

P1084

Sunnypig闯罗塔关 133人 433次 31% 2

P1085

Sunnypig闯三角关 118人 886次 13% 4

P1086

Sunnypig闯穿梭关 10人 422次 2% 5

P1087

铁人三项 93人 582次 16% 3

P1089

小胖抗日 154人 923次 17% 2

P1090

连续数之和 1480人 4001次 37% 2

P1091

环城旅行 361人 1109次 33% 2

P1092

全排列 2991人 9248次 32% 1

P1093

文科生的悲哀 5413人 11854次 46% 1

P1094

关系运算图 306人 1625次 19% 3

P1095

约瑟夫问题10E100版 654人 2357次 28% 2

P1096

津津的储蓄计划 7948人 20258次 39% 1

P1097

合并果子 5871人 26903次 22% 1

P1098

合唱队形 7157人 18285次 39% 1

P1099

虫食算 857人 3894次 22% 3

跳转 Goto >> 　第 1 2 3 4 5 6 7 8 页　添加题目　评测记录　分类筛选

111

　Copyright Vijos 高效信息学在线评测系统 © 2005-2009. www.Vijos.cn Powered by Vivian Snow　关于　联系　帮助

　Vijos Infor ---|- Total Users : 56067 | Online Users / Processes : 31 / 313 | Proc. Time : 527 ms | Current Time : 2010-4-11 15:56:15　湘ICP备06015828号