VJ 上 也有一些 线段树的板子题
题目描述
Data structure is one of the basic skills for Computer Science students, which is a particular way of storing and organizing data in a computer so that it can be used efficiently. Today let me introduce a data-structure-like problem for you.
Original, there are N numbers, namely 1, 2, 3…N. Each round, iSea find out the Ki-th smallest number and take it away, your task is reporting him the total sum of the numbers he has taken away.
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case includes two integers N, K, K indicates the round numbers. Then a line with K numbers following, indicating in i (1-based) round, iSea take away the Ki-th smallest away.
Technical Specification
1. 1 <= T <= 128
2. 1 <= K <= N <= 262 144
3. 1 <= Ki <= N - i + 1
Output
For each test case, output the case number first, then the sum.
题目大意:从1–n中每次找到第k小的数 每次查询后再把它进行删除 与 以往的线段树 不太一样
以往的线段树 不需要进行查询后进行修改
样例
Sample Input
2
3 2
1 1
10 3
3 9 1
Sample Output
Case 1: 3
Case 2: 14
blablabla
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 3e5 + 10;
typedef pair <int, int> PII;
ll res;
struct note{
int l;
int r;
int sum;
int mid()
{
return (l + r) >> 1;
}
}tre[maxn << 2];
void pushup(int rt)
{
tre[rt].sum = tre[rt * 2].sum + tre[rt * 2 + 1].sum;
}
void build(int rt , int l ,int r)
{
tre[rt].l = l, tre[rt].r = r;
if(l == r)
{
tre[rt].sum = 1;
return ;
}
int mid = tre[rt].mid();
build(rt * 2, l , mid);
build(rt * 2 + 1, mid + 1, r);
pushup(rt);
}
int query(int rt, int k) //取的是 某一个数字
{
if(tre[rt].l == tre[rt].r)//到了底部
{
tre[rt].sum = 0;
return tre[rt].l;
}
if(tre[rt * 2].sum >= k)//说明在左子树
{
int t = query(rt * 2, k);
pushup(rt);
return t;
}
else //右子树
{
int t = query(rt * 2 + 1, k - tre[rt * 2].sum);
pushup(rt);
return t;
}
pushup(rt);
}
int main()
{
int T;
scanf("%d", &T);
int cc = 1;
while(T --)
{
int n , k;
scanf("%d %d", &n, &k);
memset(tre, 0 , sizeof(tre));
build(1, 1 , n);
res = 0;
for(int i = 1 ; i <= k ; i ++)
{
int a;
scanf("%d", &a);
res += query(1, a) * 1LL;
}
printf("Case %d: %lld\n",cc ++, res);
}
return 0;
}
错误代码 (直接return 没有进行pushup 就是每次查询后没有进行及时更新 仅有query 不一样)
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 3e5 + 10;
typedef pair <int, int> PII;
ll res;
struct note{
int l;
int r;
int sum;
int mid()
{
return (l + r) >> 1;
}
}tre[maxn << 2];
void pushup(int rt)
{
tre[rt].sum = tre[rt * 2].sum + tre[rt * 2 + 1].sum;
}
void build(int rt , int l ,int r)
{
tre[rt].l = l, tre[rt].r = r;
if(l == r)
{
tre[rt].sum = 1;
return ;
}
int mid = tre[rt].mid();
build(rt * 2, l , mid);
build(rt * 2 + 1, mid + 1, r);
pushup(rt);
}
int query(int rt, int k) //取的是 某一个数字
{
if(tre[rt].l == tre[rt].r)//到了底部
{
tre[rt].sum = 0;
return tre[rt].l;
}
if(tre[rt * 2].sum >= k)//说明在左子树
{
return query(rt * 2, k);
}
else //右子树
{
return query(rt * 2 + 1, k - tre[rt * 2].sum);
}
pushup(rt);
}
int main()
{
int T;
scanf("%d", &T);
int cc = 1;
while(T --)
{
int n , k;
scanf("%d %d", &n, &k);
memset(tre, 0 , sizeof(tre));
build(1, 1 , n);
res = 0;
for(int i = 1 ; i <= k ; i ++)
{
int a;
scanf("%d", &a);
res += query(1, a) * 1LL;
}
printf("Case %d: %lld\n",cc ++, res);
}
return 0;
}