问题很简单，就是区间染色再问每种颜色染了多少个格子。问题在于范围在1~1000000000之间，直接用线段树果断会挂，但是我们可以发现给出的区间只有 N=50000个，咱就可以想到对区间进行离散化再用线段树做。先找出所有在题目中插入过的区间的端点，然后对它们进行排序，并以排序后的数组下标作为它们的新值，这样子最多只有100000个点，即区间只有1~100000，原来假设插入范围为A~B，我们在排序数组中二分找到它们的下标i,j，然后把染成某颜色的线段i,j插入线段树就可以了，这样子线段树只需要200000个节点就可以了。然后我们再把所有的出兵的区间按出兵顺序插入线段树并染色，然后再询问线段树中每一个单位区间的颜色，这里我们定义每个节点X表示的A[X],B[X]为离散后的半开半闭区间 （A[X],B[X]】，我们通过直接用下标就可以查找离散前的区间。然后线段树的插入查询都为 O(LOGN)的，则复杂度为O(NLOGN)，常数可能比较大，对于10^5 还是可以勉强过的吧。
但是关键还是线段树的区间的定义这里有问题。因为原数据可能存在X,Y相同的情况，这个时候咱当时就是直接读入的，现在感觉到不对劲了，只要把区间改为半开半闭区间，问题就可以解决了，因为 X<=Y，半开半闭X要减去1，肯定小于y的节奏。所以这样子的确就可以AC了，考试的时候调试之前的线段树就有点慌了，果然还是得多练练。
另外还有一点就是要把军队所属阵营按输入顺序输出，这就要求在输入的时候能够判重，为了能够判重，咱最好的办法便是写一个字符串的HASH函数，将HASH值存放在一个HASH表中，再用一个线性表存字符串，若HASH有重复就不加入，否则就把线性表长度加1，插入字符串。HASH函数的选取也很关键，咱选的是最简单的，令hash=hash*3+ord（s[i])*255+21
program baoweiquan;
var s:array[1..50000]of string;
site:array[1..100000]of longint;
lisan:array[0..100000]of longint;
x,y,w:array[1..50000]of longint;
hash:array[0..10000000]of longint;
ans:array[1..50000]of longint;
tot,stot,n:longint;
a,b,see,l,r:array[1..100000]of longint;
function h(s:string):longint;
var i,ss,j:longint;
begin
j:=length(s);
ss:=j;
for i:=1 to j do
ss:=(ss*3+ord(s[i])*255+21)mod 10000001;
exit(ss);
end;
procedure qsort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;j:=r;
x:=site[(l+r)shr 1];
repeat
while site[i]<x do inc(i);
while site[j]>x do dec(j);
if i<=j then begin
y:=site[i];site[i]:=site[j];site[j]:=y;
inc(i);dec(j);end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
procedure prepare;
var i:longint;
begin
lisan[0]:=1;
lisan[1]:=site[1];
for i:=2 to n*2 do
if site[i]<>site[i-1] then begin
inc(lisan[0]);lisan[lisan[0]]:=site[i];end;
end;
procedure init;
var i,j:longint;
sp:string;
begin
read(n);
stot:=0;tot:=0;
fillchar(hash,sizeof(hash),0);
for i:=1 to n do
begin
read(site[i*2-1]);
readln(site[i*2]);
x[i]:=site[i*2-1];
y[i]:=site[i*2];
readln(sp);
j:=h(sp);
if hash[j]=0 then begin
inc(stot);
s[stot]:=sp;
hash[j]:=stot;
w[i]:=stot;
end;
end;
qsort(1,n*2);
prepare;
end;
procedure build(s,t:longint);
var x,mid:longint;
begin
inc(tot);x:=tot;
a[x]:=s;b[x]:=t;see[x]:=0;
if s+1<t then begin
mid:=(s+t)shr 1;
l[x]:=tot+1;build(s,mid);
r[x]:=tot+1;build(mid,t);
end
else begin l[x]:=0;r[x]:=0;end;
end;
function find(u:longint):longint;
var l,r,mid:longint;
begin
l:=1;r:=lisan[0];
while l<=r do
begin
mid:=(l+r)shr 1;
if lisan[mid]=u then exit(mid);
if lisan[mid]>u then r:=mid-1
else l:=mid+1;
end;
exit(-1);
end;
procedure release(x:longint);
begin
if see[x]<>0 then
begin
see[l[x]]:=see[x];
see[r[x]]:=see[x];
see[x]:=0;
end;
end;
procedure insert(s,t,x,c:longint);
var mid:longint;
begin
if (a[x]>=s)and(b[x]<=t) then begin see[x]:=c;exit;end;
release(x);
mid:=(a[x]+b[x])shr 1;
if mid>s then insert(s,t,l[x],c);
if mid<t then insert(s,t,r[x],c);
end;
function query(s,t,x:longint):longint;
var mid:longint;
begin
if (a[x]+1=b[x]) then begin exit(see[x]);end;
release(x);
mid:=(a[x]+b[x])shr 1;
if mid<t then exit(query(s,t,r[x]));
if mid>s then exit(query(s,t,l[x]));
end;
procedure main;
var i,j:longint;
begin
build(0,lisan[0]*2);
for i:=1 to n do
insert(find(x[i])-1,find(y[i]),1,w[i]);
for i:=1 to lisan[0] do
begin
j:=query(i-1,i,1);
if i=1 then ans[j]:=ans[j]+1
else ans[j]:=ans[j]+lisan[i]-lisan[i-1];
end;
for i:=1 to stot do
if i=stot then write(s[i],' ',ans[i])
else writeln(s[i],' ',ans[i]);
end;
begin
init;
main;
end.
评论