第一類 區間查詢與區間求和
F. Building Numbers
time limit per test
3.0 s
memory limit per test
256 MB
input
standard input
output
standard output
In this problem, you can build a new number starting from 1, by performing the following operations as much as you need:
- Add 1 to the current number.
- Add the current number to itself (i.e. multiply it by 2).
For example, you can build number 8 starting from 1 with three operations
.
Also, you can build number 10 starting from 1 with five operations
You are given an array a consisting of n integers,
and q queries. Each query consisting of two integers l and r,
such that the answer of each query is the total number of operations you need to preform to build all the numbers in the range from l to r (inclusive)
from array a, such that each number ai (l ≤ i ≤ r) will
be built with the minimum number of operations.
Input
The first line contains an integer T (1 ≤ T ≤ 50),
where T is the number of test cases.
The first line of each test case contains two integers n and q (1 ≤ n, q ≤ 105),
where n is the size of the given array, and q is
the number of queries.
The second line of each test case contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1018),
giving the array a.
Then q lines follow, each line contains two integers l and r (1 ≤ l ≤ r ≤ n),
giving the queries.
Output
For each query, print a single line containing its answer.
Example
1
5 3
4 7 11 8 10
4 5
1 5
3 3
7
18
5
Note
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printfinstead of cin/cout in
C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in
Java.
In the first query, you need 3 operations to build number 8, and 4 operations to build number 10. So, the total number of operations is 7.
題意：給出一個數字，構成它的方法有兩種，初始值是1，可以在這基礎上自加1，或者加上它本身，然後進行區間查詢
思路：對于一個奇數，可以先自減1變成偶數後，得到可以減其自身的一個數，算出步驟數
然後用線段樹進行區間查詢
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
const int maxn=100005;
ll sum[maxn<<2],a[maxn];
int getN(ll temp)
{
int ans=0;
while(temp!=0){
if(temp%2==1){
temp--;
}else
temp/=2;
ans++;
}
return ans-1;
}
void pushup(int rt)//回溯(節點為兩個子樹之和)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
/*build函數是從底層建樹，一直回溯到根節點，自己推導可以從根節點依次二分展開整個樹*/
void build(int l,int r,int rt)
{//[l,r]表示目前節點區間，rt表示目前節點的實際存儲位置
if(l==r){//若到達葉節點
sum[rt]=a[l];
return;
}
int m=(l+r)>>1;
//左右遞歸
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
pushup(rt);
}
void update(int L,int C,int l,int r,int rt)
{//[l,r]表示目前區間，rt是目前節點編号
if(l==r){//到達葉節點，修改葉節點的值
sum[rt]=C;
return;
}
int m=(l+r)>>1;
//根據條件判斷往左子樹調用還是右
if(L<=m)
update(L,C,l,m,rt<<1);
else
update(L,C,m+1,r,rt<<1|1);
pushup(rt);//子節點的資訊更新了，是以本節點也要更新資訊
}
int query(int L,int R,int l,int r,int rt)
{//[L,R]表示要擷取區間，[l,r]表示目前區間，rt:目前節點編号
if(L<=l&&r<=R){ //在區間内直接傳回
return sum[rt];
}
int m=(l+r)>>1;
//左子區間:[l,m] 右子區間：[m+1,r] 求和區間:[L,R]
//累加答案
int ans=0;
if(L<=m){
int temp=query(L,R,l,m,rt<<1);//左子區間與[L,R]有重疊，遞歸
ans=temp+ans;
}
if(R>m){
int temp=query(L,R,m+1,r,rt<<1|1);//右子區間與[L,R]有重疊，遞歸
ans=temp+ans;
}
return ans;
}
int main()
{
// freopen("in.txt","r",stdin);
int i,x,y;
int m,n,T,q;
ll temp;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++){
scanf("%lld",&temp);
a[i]=getN(temp);
// cout<<a[i]<<endl;
}
build(1,n,1);//開始建樹
while(q--)
{
scanf("%d%d",&x,&y);
printf("%d\n",query(x,y,1,n,1));
}
}
}
第二類 求矩形并的面積
Atlantis
Description There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity. The input consists of several test cases. Each test case starts with a line containing a single integer n (1 <= n <= 100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area. The input file is terminated by a line containing a single 0. Don't process it. For each test case, your program should output one section. The first line of each section must be "Test case #k", where k is the number of the test case (starting with 1). The second one must be "Total explored area: a", where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point. Output a blank line after each test case. Sample Input Source Mid-Central European Regional Contest 2000 |
[Submit] [Go Back] [Status]
[Discuss]
/*
* 本題中的坐标是浮點類型的, 故不能将坐标直接離散.我們必須為它們建立一個對應關系,
* 用一個整數去對應一個浮點數這樣的對應關系在本題的數組y[]中。
*/
struct node
{
int st, ed, c; // c: 區間被覆寫的層數, m: 區間的測度
double m;
} ST[802];
struct line
{
double x, y1, y2; // 縱方向直線, x:直線橫坐标, y1 y2:直線上的下面與上面的兩個縱坐标
bool s; // s = 1 : 直線為矩形的左邊, s = 0:直線為矩形的右邊
} Line[205];
double y[205], ty[205]; // y[]整數與浮點數的對應數組; ty[]:用來求y[]的輔助數組
void build(int root, int st, int ed)
{
ST[root].st = st;
ST[root].ed = ed;
ST[root].c = 0;
ST[root].m = 0;
if (ed - st > 1)
{
int mid = (st + ed) / 2;
build(root * 2, st, mid);
build(root * 2 + 1, mid, ed);
}
return ;
}
void updata(int root)
{
if (ST[root].c > 0)
{ // 将線段樹上區間的端點分别映射到y[]數組所對應的浮點數上,由此計算出測度
ST[root].m = y[ST[root].ed - 1] - y[ST[root].st - 1];
}
else if (ST[root].ed - ST[root].st == 1)
{
ST[root].m = 0;
}
else
{
ST[root].m = ST[root * 2].m + ST[root * 2 + 1].m;
}
return ;
}
void insert(int root, int st, int ed)
{
if (st <= ST[root].st && ST[root].ed <= ed)
{
ST[root].c++;
updata(root);
return ;
}
if (ST[root].ed - ST[root].st == 1)
{
return ; // 不出錯的話 這句話就是備援的
}
int mid = (ST[root].ed + ST[root].st) / 2;
if (st < mid)
{
insert(root * 2, st, ed);
}
if (ed > mid)
{
insert(root * 2 + 1, st, ed);
}
updata(root);
return ;
}
void Delete(int root, int st, int ed)
{
if (st <= ST[root].st && ST[root].ed <= ed)
{
ST[root].c--;
updata(root);
return ;
}
if (ST[root].ed - ST[root].st == 1)
{
return ; // 不出錯的話 這句話就是備援的
}
int mid = (ST[root].st + ST[root].ed) / 2;
if (st < mid)
{
Delete(root * 2, st, ed);
}
if (ed > mid)
{
Delete(root * 2 + 1, st, ed);
}
updata(root);
return ;
}
int Correspond(int n, double t)
{
// 二分查找出浮點數t在數組y[]中的位置(此即所謂的映射關系)
int low, high, mid;
low = 0;
high = n - 1;
while (low < high)
{
mid = (low + high) / 2;
if (t > y[mid])
{
low = mid + 1;
}
else
{
high = mid;
}
}
return high + 1;
}
bool cmp(line l1, line l2)
{
return l1.x < l2.x;
}
int main()
{
int n, i, num, l, r, c = 0;
double area, x1, x2, y1, y2;
while (cin >> n, n)
{
for (i = 0; i < n; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
Line[2 * i].x = x1;
Line[2 * i].y1 = y1;
Line[2 * i].y2 = y2;
Line[2 * i].s = 1;
Line[2 * i + 1].x = x2;
Line[2 * i + 1].y1 = y1;
Line[2 * i + 1].y2 = y2;
Line[2 * i + 1].s = 0;
ty[2 * i] = y1;
ty[2 * i + 1] = y2;
}
n <<= 1;
sort(Line, Line + n, cmp);
sort(ty, ty + n);
y[0] = ty[0];
// 處理數組ty[]使之不含重覆元素,得到新的數組存放到數組y[]中
for (i = num = 1; i < n; i++)
{
if (ty[i] != ty[i - 1])
{
y[num++] = ty[i];
}
}
build(1, 1, num); // 樹的葉子節點與數組y[]中的元素個數相同,以便建立一一對應的關系
area = 0;
for (i = 0; i < n - 1; i++)
{ // 由對應關系計算出線段兩端在樹中的位置
l = Correspond(num, Line[i].y1);
r = Correspond(num, Line[i].y2);
if (Line[i].s) // 插入矩形的左邊
{
insert(1, l, r);
}
else // 删除矩形的右邊
{
Delete(1, l, r);
}
area += ST[1].m * (Line[i + 1].x - Line[i].x);
}
cout << "Test case #" << ++c << endl << "Total explored area: ";
cout << fixed << setprecision(2) << area << endl << endl; // 需要引入iomanip頭檔案
}
return 0;
} 第三類 求矩形并的周長（線段樹+離散化+掃描線）
Picture
A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter. Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1. The vertices of all rectangles have integer coordinates. Your program is to read from standard input. The first line contains the number of rectangles pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate. 0 <= number of rectangles < 5000 All coordinates are in the range [-10000,10000] and any existing rectangle has a positive area. Your program is to write to standard output. The output must contain a single line with a non-negative integer which corresponds to the perimeter for the input rectangles. |
struct node
{
int st, ed, m, lbd, rbd;
int sequence_line, count;
} ST[40005];
void build(int st, int ed, int v) // 建樹,區間為[st, ed]
{
ST[v].st = st;
ST[v].ed = ed;
ST[v].m = ST[v].lbd = ST[v].rbd = 0;
ST[v].sequence_line = ST[v].count = 0;
if (ed - st > 1)
{
int mid = (st + ed) / 2;
build(st, mid, 2 * v + 1);
build(mid, ed, 2 * v + 2);
}
return ;
}
void UpData(int v) // 更新結點區間的測度
{
if (ST[v].count > 0)
{
ST[v].m = ST[v].ed - ST[v].st;
ST[v].lbd = ST[v].rbd = 1;
ST[v].sequence_line = 1;
return ;
}
if (ST[v].ed - ST[v].st == 1)
{
ST[v].m = 0;
ST[v].lbd = ST[v].rbd = 0;
ST[v].sequence_line = 0;
}
else
{
int left = 2 * v + 1, right = 2 * v + 2;
ST[v].m = ST[left].m + ST[right].m;
ST[v].sequence_line = ST[left].sequence_line + ST[right].sequence_line - (ST[left].rbd & ST[right].lbd);
ST[v].lbd = ST[left].lbd;
ST[v].rbd = ST[right].rbd;
}
return ;
}
void insert(int st, int ed, int v)
{
if (st <= ST[v].st && ed >= ST[v].ed)
{
ST[v].count++;
UpData(v);
return ;
}
int mid = (ST[v].st + ST[v].ed) / 2;
if (st < mid)
{
insert(st, ed, 2 * v + 1);
}
if (ed > mid)
{
insert(st, ed, 2 * v + 2);
}
UpData(v);
return ;
}
void Delete(int st, int ed, int v)
{
if (st <= ST[v].st && ed >= ST[v].ed)
{
ST[v].count--;
UpData(v);
return ;
}
int mid = (ST[v].st + ST[v].ed) / 2;
if (st < mid)
{
Delete(st, ed, 2 * v + 1);
}
if (ed > mid)
{
Delete(st, ed, 2 * v + 2);
}
UpData(v);
return ;
}
struct line
{
int x, y1, y2; // y1 < y2
bool d; // d=true表示該線段為矩形左邊,d=false表示該線段為矩形的右邊
} a[10003];
bool cmp(line t1, line t2) // 為線段排序的函數,友善從左向右的掃描
{
return t1.x < t2.x;
}
void cal_C(int n);
int main()
{
int n, x1, x2, y1, y2, i, j, suby, upy;
while (scanf("%d",&n) != EOF)
{
j = 0;
suby = 10000;
upy = -10000;
for (i = 0; i < n; i++)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
a[j].x = x1;
a[j].y1 = y1;
a[j].y2 = y2;
a[j].d = 1;
j++;
a[j].x = x2;
a[j].y1 = y1;
a[j].y2 = y2;
a[j].d = 0;
j++;
if (suby > y1)
{
suby = y1;
}
if (upy < y2)
{
upy = y2;
}
}
sort(a, a + j, cmp);
build(suby, upy, 0);
cal_C(j);
}
return 0;
}
void cal_C(int n)
{
int i, t2, sum = 0;
t2 = 0;
a[n] = a[n - 1];
for (i = 0; i < n; i++)
{
if (a[i].d == 1)
{
insert(a[i].y1, a[i].y2, 0);
}
else
{
Delete(a[i].y1, a[i].y2, 0);
}
sum += ST[0].sequence_line * (a[i + 1].x - a[i].x) * 2;
sum += abs(ST[0].m - t2);
t2 = ST[0].m;
}
printf("%d\n", sum);
}