fzu_noip 1040(继任者-离线排序插入+区间最值)

继任者

时限:1s内存:32M

★问题描述:

S开了家公司,他自己是老板,其余员工都有一名直系上级,每名员工都有对公司的忠诚度和能力值。S时不时会开除某名员工,由其下属中能力值大于这名员工的人中忠诚度最高的担任其职务。他想知道,若开除某名员工,该选谁担任其职务。A是B的下属是指,A的直系上级是B或B的下属。

★数据输入:

第一行输入T表示CASE数。接下来T组数据,每组数据第一行输入两个整数n,m(2<=n,m<=25000),表示有该公司包括S有n个人,有m组询问。员工按输入顺序从1到n-1编号,S编号为0。接下去1到n-1行,每行三个整数a,b,c(0<=a<=n-1,0<=b,c<=1000000)分别表示第i名员工的直系上级编号、忠诚度、能力值,每名员工的编号大于其上级的编号,且他们的忠诚度各不相同。接下去m行,每行一个整数q(1<=q<=n-1)表示询问若开除第q名员工应该选谁担任其职务。注意询问并没有真正开除员工,也就是说各个询问假设要开除的员工互不影响。

★结果输出:

对于每个询问输出一个数表示该选的员工的编号,若这样的员工不存在则输出-1。

输入示例

输出示例

1

3 2

0 100 99

1 101 100

1

2

2

-1

 本来是按B值对结点从大到小排序-然后按顺序插入线段树

因为插入前结点所对应的区间一定只有比父节点B值大的,因此直接输出A值最大的即可(线段树)

实际做法:暴力插入结点,直到找到根或找到比它A,B值都大(这样上司选它一定更优)的为止。


#include<cstdio>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (25000+10)
#define MAXCi (1000000)
int n,m;
struct node
{
    int key,fim,fa,ans;
    node():ans(-1){}
    node(int _key,int _fim,int _fa):key(_key),fim(_fim),fa(_fa),ans(-1){}
}a[MAXN];
void update(int x)
{
     for (int now=a[x].fa;now;now=a[now].fa)
     {
         if (a[x].key>a[now].key&&(a[now].ans==-1||a[a[now].ans].fim<a[x].fim)) a[now].ans=x;
         else if (a[x].key<a[now].key&&a[x].fim<a[now].fim) break;
     }
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n-1;i++)
    {
        cin>>a[i].fa>>a[i].fim>>a[i].key;update(i);
    }
    for (int i=1;i<=m;i++)
    {
        int p;
        cin>>p;
        cout<<a[p].ans<<endl;
    }
    return 0;
}

POJ 3468(成段更新)

Language:
线段树的成段更新
Time Limit: 5000MS   Memory Limit: 131072K
Total Submissions: 38010   Accepted: 11017
Case Time Limit: 2000MS

Description

对于数列 A1A2, ... , AN. 你要进行2个操作:将一个区间的数同加上某个数,输出一段区间的和。

Input

第一行2个整数表示数列长度和操作次数. 1 ≤ N,Q ≤ 100000.
第二行为数列 A1A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
接下来的Q行操作:
"C a b c" 表示将 AaAa+1, ... , Ab.加上c. -10000 ≤ c ≤ 10000.
"Q a b" 输出区间[a,b]的和。

Output

输出所有询问的答案,每行1个。

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

Hint

longint会爆的。

Source



显然这题是线段树。

但是我之前习惯的nowl和nowr似乎太费解了(以致于我自己都要想半天)

回去看看其它人咋写……


Program poj3468;
const
   maxn=100000;
   maxq=100000;
var
   n,m,i,j,k:longint;
   lazy,t:array[1..maxn*8] of int64;
   c:char;
Procedure pushup(root:longint);
begin
   t[root]:=t[root*2]+t[root*2+1];
end;
Procedure build(l,r,root:longint);
var
   m:longint;
begin
   if (l=r) then
   begin
      read(t[root]);
      exit;
   end;
   m:=(l+r) shr 1;
   build(l,m,root*2);
   build(m+1,r,root*2+1);
   pushup(root);
end;
Procedure Pushdown(l,r,root:longint);
var
   m:longint;
begin
   m:=(l+r) shr 1;
   if (lazy[root]=0) then exit;
   inc(lazy[root shl 1],lazy[root]);
   inc(lazy[root shl 1+1],lazy[root]);
   inc(t[root shl 1],lazy[root]*(m-l+1));
   inc(t[root shl 1+1],lazy[root]*(r-(m+1)+1));

   lazy[root]:=0;
end;
Procedure update(l,r,nowl,nowr,root,cost:longint);
var
   m:longint;
begin
   if (l<=nowl) and (nowr<=r) then
   begin
      inc(lazy[root],cost);
      inc(t[root],(nowr-nowl+1)*cost);
      exit;
   end;
   pushdown(nowl,nowr,root);
   m:=(nowl+nowr) shr 1;
   if (l<=m) then update(l,r,nowl,m,root*2,cost);
   if (m+1<=r) then update(l,r,m+1,nowr,root*2+1,cost);
   pushup(root);
end;
function query(l,r,nowl,nowr,root:longint):int64;
var
   m:longint;
   res:int64;
begin
   if (l<=nowl) and (nowr<=r) then
   begin
      exit(t[root]);
   end;
   pushdown(nowl,nowr,root);
   m:=(nowl+nowr) shr 1;
   res:=0;
   if (l<=m) then res:=res+query(l,r,nowl,m,root*2);
   if (m+1<=r) then res:=res+query(l,r,m+1,nowr,root*2+1);
   exit(res);
end;


begin
   readln(n,m);
   fillchar(lazy,sizeof(lazy),0);
   build(1,n,1);
   readln;
   while (m>0) do
   begin
      read(c);
      if c='Q' then
      begin
         readln(i,j);
         writeln(query(i,j,1,n,1));
      end
      else
      begin
         readln(i,j,k);
         update(i,j,1,n,1,k);
      end;



      dec(m);
   end;
end.

接下来再来说说zkw线段树的解法:

这涉及到原数组A,差分数组A‘,差分数组前缀前缀和A'':

首先,它们3者满足如下关系:
1.差分数组的前缀和SA[i]'为原数组A[i](定义)。
2.原数组的前缀和SA[I]为差分数组的前缀前缀和A''[i];


接下来我们分别建立A‘和(i*A')的{单点修改,区间求和}线段树
显然要想知道

A[i]+A[i+1]+....A[ j ]
     =SA[ j ]-SA[ i -1]
     =A''[ j  ] - A'' [ i-1 ]
     =(SA'[1] +SA'[2]+...SA''[ j ] )- (SA'[1] +SA'[2]+...SA''[ i-1 ] )
     ={ j *A'[1] +(j-1)'A'[2]+....A'[ j ]}-{ (i-1) *A'[1] +(i-2)'A'[2]+....A'[ i-1 ]  }
     ={  (j+1)*(A'[1]+A'[2]+...A'[ j ] )-(1*A'[1]+2*A'[2]+...j*A'[ j ]  }  -  {   i*(A'[1]+A'[2]+...A'[ i-1 ] )-(1*A'[1]+2*A'[2]+...(i-1)*A'[ i-1 ]  }

这个方程如果看起来乱的话就直接看上面的图A''(相当于原数组前缀和SA-请想办法表示成A‘的累加形式)

显然如果将一个区间[A,B]+V,对3个数组影响如下:


幸运的是,我们只要维护A‘和{i*A’}
A和A‘’都要折腾一段区间,只有A'只要修改头和(尾+1)(如果存在)

那么{i*A‘} 的 维护 也只要修改2个节点 (请注意每个A‘ 实际上是独立的),同上:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100000+10)
#define MAXAi (1000000000)
#define MAXCi (10000)
__int64 a[MAXN];
int n,q;
char c[10];
class SegMentTree
{
public:
	int M;
	__int64 t[MAXN*10];
	void fillchar()
	{
		M=1;while (M-2<n) M<<=1;
		memset(t,0,sizeof(t));
	}
	__int64 h(__int64 x,__int64 y)
	{
		return x+y;
	}
	void update(int x,__int64 c)
	{
		for (x>>=1;x;x>>=1) t[x]=t[x]+c;
	}
	void insert(int x,__int64 c)
	{
		x+=M;
		t[x]+=c;
		update(x,c);
	}
	__int64 find(int l,int r)
	{
		l=l-1+M;r=r+1+M;
		__int64 ans=0;
		while (l^r^1)
		{
			if (~l&1) {ans+=t[l+1];/* cout<<l+1<<' ';*/}
			if (r&1)  {ans+=t[r-1];/* cout<<r-1<<' ';*/}
			l>>=1;r>>=1;
		}
//		cout<<ans<<' ';
		return ans;
	}
	/*
	void print()
	{
		for (int i=1;i<=M*2;i++) if (t[i]!=0) cout<<i<<':'<<t[i]<<' ';
		cout<<endl;
	}
	*/

}t_ai,t_iai;
int main()
{
//	freopen("Poj3468.in","r",stdin);
	scanf("%d%d",&n,&q);t_ai.fillchar();t_iai.fillchar();
	a[0]=0;for (int i=1;i<=n;i++) scanf("%I64d",&a[i]);
	for (int i=1;i<=n;i++)
	{
		t_ai.insert(i,a[i]-a[i-1]);
		t_iai.insert(i,i*(a[i]-a[i-1]));
	}
	for (int i=1;i<=q;i++)
	{
		scanf("%s",c);
		if (c[0]=='Q')
		{
			int p1,p2;
			scanf("%d%d",&p1,&p2);p1--;
			__int64 ans1=(p1>0)?(__int64)(t_ai.find(1,p1)*(__int64)((__int64)p1+1)-(__int64)t_iai.find(1,p1)):0;//cout<<ans1<<endl;
			__int64 ans2=(__int64)t_ai.find(1,p2)*(__int64)(p2+1)-(__int64)t_iai.find(1,p2);//cout<<ans2<<endl;
			cout<<(__int64)(ans2-ans1)<<endl;
		}
		else
		{
			int l,r;
			__int64 c;
			scanf("%d%d%I64d",&l,&r,&c);
			t_ai.insert(l,(__int64)c);
			t_iai.insert(l,(__int64)c*l);
			if (r<n)
			{
				t_ai.insert(r+1,-(__int64)c);
				t_iai.insert(r+1,-(__int64)c*(__int64)(r+1));
			}
		}
//		t_ai.print();
//		t_iai.print();
	}


	return 0;
}









POJ 2777(涂点问线)

线段树……

Program p2777;
const
   maxl=100000;
   maxt=30;
   maxo=100000;
var
   l,t,o,i,j,k:longint;
   col:array[1..maxl*10] of longint;
   c:char;
   x,y,color:longint;
   visit:array[1..maxt] of boolean;
procedure build(l,r,root:longint);
var
   mid:longint;
begin
   if l=r then
   begin
      col[root]:=1;
      exit;
   end;
   mid:=(l+r) shr 1;
   build(l,mid,root shl  1);
   build(mid+1,r,root shl 1+1);
   col[root]:=1;
end;
procedure swap(var a,b:longint);
var
   p:longint;
begin
   p:=a;a:=b;b:=p;
end;
procedure detate(l,r,sonl,sonr,root,color:longint);
var
   i,j,mid:longint;
begin
   mid:=(l+r) shr 1;
   if l=r then
   begin
      col[root]:=color;
      exit;
   end;

   if (sonl<=l) and (r<=sonr) then
   begin
      col[root]:=color;
      exit;
   end;

   if col[root]>0 then
   begin
      col[root*2]:=col[root];
      col[root*2+1]:=col[root];
      col[root]:=-1;


   end;

   if not((mid<sonl) or (sonr<l)) then detate(l,mid,sonl,sonr,root shl 1,color);
   if not((r<sonl) or (sonr<mid+1)) then detate(mid+1,r,sonl,sonr,root shl 1+1,color);



end;
function quere(l,r,sonl,sonr,root:longint):longint;
var
   mid,i,j:longint;
begin
   quere:=0;
   mid:=(l+r) shr 1;

   if col[root]>0 then
   begin
      if not(visit[col[root]]) then
      begin
         visit[col[root]]:=true;
         exit(1);
      end;
      exit(0);
   end;


   if not((mid<sonl) or (sonr<l)) then inc(quere,quere(l,mid,sonl,sonr,root shl 1));
   if not((r<sonl) or (sonr<mid+1)) then inc(quere,quere(mid+1,r,sonl,sonr,root shl 1+1));


end;

begin
   readln(l,t,o);
   build(1,l,1);
   for i:=1 to o do
   begin
      read(c);
      if c='C' then
      begin
         readln(x,y,color);
         if x>y then swap(x,y);
         detate(1,l,x,y,1,color);
      end
      else
      begin
         readln(x,y);
         if x>y then swap(x,y);
         fillchar(visit,sizeof(visit),false);
         writeln(quere(1,l,x,y,1));
      end;
   end;
end.

POJ 2828(卡时线段树)

本题乍一看链表,实际上肯定超时%……

故用线段树 LogN查找……

Program P2828;
const
   maxn=200000;
var
   n,i,j:longint;
   pos,val:array[1..maxn] of longint;
   sum:array[1..maxn*10] of longint;
   ans:array[1..maxn] of longint;
procedure pushup(root:longint);
begin
   sum[root]:=sum[root*2]+sum[root*2+1];
end;
procedure build(l,r,root:longint);
var
   mid:longint;
begin
   if l=r then
   begin
      sum[root]:=1;
      exit;
   end;
   mid:=(l+r) shr 1;
   build(l,mid,root*2);
   build(mid+1,r,root*2+1);
   pushup(root);
end;
procedure decr(l,r,root,node:longint);
var
   mid:longint;
begin
   if l=r then
   begin
      dec(sum[root]);
      exit;
   end;
   mid:=(l+r) shr 1;
   if (node<=mid) then decr(l,mid,root shl 1,node)
   else decr(mid+1,r,root shl 1+1,node);
   pushup(root);
end;
function find(l,r,root,value:longint):longint;
var
   mid:longint;
begin
   mid:=(l+r) shr 1;
   if l=r then
   begin
      decr(1,n,1,l);
      exit(l);
   end;
   if (sum[root shl 1]>=value) then exit(find(l,mid,root shl 1,value))
   else exit(find(mid+1,r,root shl 1+1,value-sum[root shl 1]));
end;
begin
   while not seekeof do
   begin
      read(n);
      for i:=1 to n do read(pos[i],val[i]);
      build(1,n,1);
      for i:=n downto 1 do
      begin
         ans[find(1,n,1,pos[i]+1)]:=val[i];

      end;
      for i:=1 to n-1 do write(ans[i],' ');
      writeln(ans[n]);
   end;
end.

POJ 2528(数据有误的线段树)

此题数据有误……

是我英文太差,还是答案出错……

Program P2528;
const
   maxn=10000;
   maxr=10000000;
var
   t,n,i,j,k:longint;
   a,b,v:array[1..maxn*2] of longint;
   h:array[1..maxr] of longint;
   col:array[1..maxn*100] of longint;
   visit:array[1..maxn*2] of boolean;


procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;
   j:=r;
   m:=v[(l+r) div 2];
   repeat
      while v[i]<m do inc(i);
      while v[j]>m do dec(j);
      if i<=j then
      begin
         p:=v[i];
         v[i]:=v[j];
         v[j]:=p;
         inc(i);
         dec(j);
      end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);
end;
procedure update(l,r,sonl,sonr,root,color:longint);
var
   i,j,k,mid:longint;
begin
   mid:=(l+r) shr 1;
   if (sonl<=l) and (r<=sonr) then
   begin
      col[root]:=color;
      exit;
   end;

   if (col[root]>=0) then
   begin
      col[root*2]:=col[root];
      col[root*2+1]:=col[root];
      col[root]:=-1;
   end;
   if not((mid<sonl) or (sonr<l)) then update(l,mid,sonl,sonr,root*2,color);
   if not((r<sonl) or (sonr<mid+1)) then update(mid+1,r,sonl,sonr,root*2+1,color);



end;
function dfs(l,r,root:longint):longint;
var
   i,j,mid:longint;
begin
   mid:=(l+r) shr 1;
   if col[root]=0 then exit(0);
   if col[root]>0 then
   begin
      if not(visit[col[root]]) then
      begin
         visit[col[root]]:=true;
         exit(1);
      end
      else exit(0);
   end;

   exit(dfs(l,mid,root*2)+dfs(mid+1,r,root*2+1));

end;
begin
   read(t);
   while t>0 do
   begin
      dec(t);
      read(n);
      for i:=1 to n do
      begin
         read(a[i],b[i]);
         v[i]:=a[i];
         v[n+i]:=b[i];
      end;
      qsort(1,2*n);
      j:=1;
      for i:=2 to 2*n do
         if v[i]<>v[i-1] then
         begin
            inc(j);
            v[j]:=v[i];
         end;
      for i:=1 to j do h[v[i]]:=i;

      fillchar(col,sizeof(col),0);

      for i:=1 to n do
      begin
        update(1,j,h[a[i]],h[b[i]],1,i);
      end;
      fillchar(visit,sizeof(visit),false);
      writeln(dfs(1,j,1));

   end;
end.

线段树-模板

PushUp(root) 维护

          sum[root]=sum[root/2]+sum[root/2+1] 

Build     建树 (当前区间,序号(当前区间的root))

         维护目前结点

l=r   return

    更新左右子树

Update   更新子节点 (当前区间,所求区间,Root)

l=r    更新   return

更新结点在左子树    更新左子树

否则更新右子树

PushUp 当前结点

Query 区间求和 (当前区间,所求区间,Root)

包含   直接返回当前值

否则考察左右结点是否包含   求和