树状数组 要一点思考

一开始块排敲错两次

 1 program hehe;
 2 var
 3  t,n,m,i,j,k:longint;
 4  c:array[0..1000000] of longint;
 5  pre,next,a,x:array[0..50005] of longint;
 6  ans,p,z,y:array[0..200005] of longint;
 7
 8   procedure sort(l,r:longint);
 9   var
10    zuo,you,mid:longint;
11   begin
12    zuo:=l;
13    you:=r;
14    mid:=y[(l+r)>>1];
15    repeat
16     while y[zuo]<mid do inc(zuo);
17     while y[you]>mid do dec(you);
18     if zuo<=you then
19     begin
20      t:=z[zuo];
21      z[zuo]:=z[you];
22      z[you]:=t;
23      t:=y[zuo];
24      y[zuo]:=y[you];
25      y[you]:=t;
26      t:=p[zuo];
27      p[zuo]:=p[you];
28      p[you]:=t;
29      dec(you);
30      inc(zuo);
31     end;
32    until zuo>you;
33    if l<you then sort(l,you);
34    if zuo<r then sort(zuo,r);
35   end;
36
37   function lowbit(a:longint):longint;
38   begin
39    exit(a and(-a));
40   end;
41
42   procedure add(a,b:longint);
43   begin
44    while a<=n do
45    begin
46     x[a]:=x[a]+b;
47     a:=a+lowbit(a);
48    end;
49   end;
50
51   function find(a:longint):longint;
52   var
53    s:longint;
54   begin
55    s:=0;
56    while a>0 do
57    begin
58     s:=s+x[a];
59     a:=a-lowbit(a);
60    end;
61    exit(s);
62   end;
63
64 begin
65  readln(n);
66  fillchar(a,sizeof(a),255);
67  for i:=1 to n do
68  begin
69   read(a[i]);
70   pre[i]:=c[a[i]];
71   c[a[i]]:=i;
72   next[pre[i]]:=i;
73  end;
74  read(m);
75  for i:=1 to m do read(z[i],y[i]);
76  for i:=1 to m do p[i]:=i;
77  sort(1,m);
78  for i:=1 to m do
79  begin
80   while j<y[i] do
81   begin
82    inc(j);
83    add(pre[j]+1,1);
84    add(j+1,-1)
85   end;
86   ans[p[i]]:=find(z[i]);
87  end;
88  for i:=1 to m do
89  writeln(ans[i]);
90 end.

1878: [SDOI2009]HH的项链

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 2154  Solved: 1062
[Submit][Status][Discuss]

Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运,所以每次散步 完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH不断地收集新的贝壳,因此, 他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同 的贝壳?这个问题很难回答。。。因为项链实在是太长了。于是,他只好求助睿智的你,来解 决这个问题。

Input

第一行:一个整数N,表示项链的长度。 第二行:N个整数,表示依次表示项链中贝壳的编号(编号为0到1000000之间的整数)。 第三行:一个整数M,表示HH询问的个数。 接下来M行:每行两个整数,L和R(1 ≤ L ≤ R ≤ N),表示询问的区间。

Output

M行,每行一个整数,依次表示询问对应的答案。

Sample Input

6
1 2 3 4 3 5
3
1 2
3 5
2 6

Sample Output

2
2
4

HINT

对于20%的数据,N ≤ 100,M ≤ 1000;
对于40%的数据,N ≤ 3000,M ≤ 200000;
对于100%的数据,N ≤ 50000,M ≤ 200000。

Source

Day2

[Submit][Status][Discuss]

时间: 06-17

树状数组 要一点思考的相关文章

一维 + 二维树状数组 + 单点更新 + 区间更新 详解

树状数组详解: 假设一维数组为A[i](i=1,2,...n),则与它对应的树状数组C[i](i=1,2,...n)是这样定义的: C1 = A1 C2 = A1 + A2 C3 = A3 C4 = A1 + A2 + A3 + A4 C5 = A5 C6 = A5 + A6 ................. C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 ................ 如图可知: 为奇数的时候他是代表他本身,而为偶数的时候则是代表着自

POJ 2155 Matrix(二维树状数组)

题意:有一个矩阵,每次操作可以是编辑某个矩形区域,这个区域的0改为1,1改为0,每次查询只查询某一个点的值是0还是1.  思路:这道题和一般的树状数组有一点不同,这道题是区间修改,单点查询,而树状数组处理的是单点修改,所以我们可以改一下矩阵里的每一个值代表的意义.可以注意到我们只关注一个点被翻转了奇数次还是偶数次,令矩阵的元素a[i][j]表示矩形区域(1,1)到(i,j)的修改次数,这样我们可以把区间修改转化为四个端点的单点修改,即modify(x2, y2, 1); modify(x1-

树状数组初步

树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构.主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值:经过简单修改可 以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值,且其常数之小是线段树无法做到的. 如图,其中a数组保存了初始读入的n个值,c数组即为我们构建的树状数组. 那么容易发现: C1 = A1 C2 = A1 + A2 C3 = A3 C4 = A1 + A

UVA 10869 - Brownie Points II(树状数组)

UVA 10869 - Brownie Points II 题目链接 题意:平面上n个点,两个人,第一个人先选一条经过点的垂直x轴的线,然后另一个人在这条线上穿过的点选一点作垂直该直线的线,然后划分出4个象限,第一个人得到分数为1,3象限,第二个人为二四象限,问第一个个人按最优取法,能得到最小分数的最大值,和这个值下另一个人的得分可能情况 思路:树状数组,可以枚举一点,如果能求出右上和左下点的个数就好办了,其实用一个树状数组,把y坐标离散化掉,然后记录进来,然后把点按x从左往右,每次删掉点后查询

【bzoj1146】[CTSC2008]网络管理Network 倍增LCA+dfs序+树状数组+主席树

题目描述 M公司是一个非常庞大的跨国公司,在许多国家都设有它的下属分支机构或部门.为了让分布在世界各地的N个部门之间协同工作,公司搭建了一个连接整个公司的通信网络.该网络的结构由N个路由器和N-1条高速光缆组成.每个部门都有一个专属的路由器,部门局域网内的所有机器都联向这个路由器,然后再通过这个通信子网与其他部门进行通信联络.该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信. 高速光缆的数据传输速度非常快,以至于利用光缆传输的延迟时间可以忽略.但是由于路由器老化,在这些

求逆序数数目(树状数组+离散化)

404在玩忍者印记(Mark of the Ninja)操纵忍者时遇到这样一个场景,两栋大楼之间有许多绳索,从侧面看,就像这个样子: 我们的忍者非常有好奇心,他可以观察到每个绳索的端点在两栋楼的高度,想知道这些绳索有多少个交点(图中黑色的点).他观察到不会建筑上不会有一点上有两个绳索,并且没有三条绳索共点. 输入描述 第一行:整数T,代表有T组数据. (1 <= T <= 100) 下一行:整数N,代表有N条绳索. (1 <= N <= 100000) 接下来Na行给出两个整数A_

树状数组

树状数组                   转自:      By 岩之痕  http://blog.csdn.net/zearot/article/details/45028723 一.概述 树状数组是一种 用数组进行存储的 自下而上进行操作的  多叉树. 以下叙述中,A为原数组,C为树状数组所用的数组,B为特殊情况需要用到的辅助数组. 最基本的应用就是维护一个支持两种操作的数列:1.让A[i]加上某数X     2.求一个区间A[L] + A[L+1] + ... + A[R] 的和. 树

BZOJ 2758 Blinker的噩梦(扫描线+熟练剖分+树状数组)

题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=2758 题意:平面上有n个多边形(凸包和圆).任意两个多边形AB只有两种关系:(1)A包含B或者B包含A:(2)AB的公共面积为0.每个多边形有一个值x.m个查询.分两种:(1)修改某个多边形的值:(2)从一点s走到另一点t.每次走出一个多边形或者进入一个多边形时,都要抑或上该多边形的值.输出走到t时的值.(由抑或的性质和本题定义可得这个值跟走的路经无关) 思路:首先我们发现,这些

树状数组求逆序对:POJ 2299、3067

前几天开始看树状数组了,然后开始找题来刷. 首先是 POJ 2299 Ultra-QuickSort: http://poj.org/problem?id=2299 这题是指给你一个无序序列,只能交换相邻的两数使它有序,要你求出交换的次数.实质上就是求逆序对,网上有很多人说它的原理是冒泡排序,可以用归并排序来求出,但我一时间想不出它是如何和归并排序搭上边的(当初排序没学好啊~),只好用刚学过的树状数组来解决了.在POJ 1990中学到了如何在实际中应用上树状数组,没错,就是用个特殊的数组来记录即