1 A - Super Mario
这道题要求某区间内比h小的个数，其实这里可以类似于树状数组求逆序数那样。关键是如何转换成树状数组的模型，这才是本题的难点。
我们首先分析，如果知道h在该区间的哪个位置，那么剩下的就很好做了。我们还可以发现，如果找到了当前的比h小的所有点（大于的点我们先忽略掉），那么我们就可以用树状数组求它的[l,r]区间的和。这样就跟树状数组有了一点联系，但是还不够，因为我们发现，h的大小会影响我们所要找的区间。什么意思呢？就是我们先找到的是h1，再找h2，但h1>h2，就会出现这样的问题：h1所对应的区间找到了，但再找h2时，它对应的区间中可能会有比h2大的数，这样就不符合条件了。所以说这里有一个离线算法，就是先把所有的询问存下来，再按照h的大小进行从小到大排序，然后根据h的大小，从小到大地一个个插入所有区间内的数，这样就符合条件了。
-
#include<iostream>
-
#include<cstdio>
-
#include<cstring>
-
#include<algorithm>
-
using
namespace std;
-
-
const
int maxn =
1e5+
5;
-
struct
Query
-
{
-
int l,r,h;
-
int id;
-
bool
operator < (Query a)
-
{
-
return h < a.h;
-
}
-
}q[maxn];
-
struct
Node
-
{
-
int num;
-
int id;
-
bool
operator < (Node a)
-
{
-
return num < a.num;
-
}
-
}a[maxn];
-
int n,m;
-
int tree[maxn<<
2],ans[maxn];
-
-
int lowbit(int x)
-
{
-
return x & (-x);
-
}
-
-
void update(int x,int d)
-
{
-
for(
int i = x; i <= n; i +=
lowbit(i))
-
tree[i] += d;
-
}
-
-
int getsum(int x)
-
{
-
int sum =
0;
-
for(
int i = x; i >
0; i -=
lowbit(i))
-
sum += tree[i];
-
return sum;
-
}
-
-
int main()
-
{
-
int t,cas =
1;
-
cin >> t;
-
while(t--)
-
{
-
cin >> n >> m;
-
for(
int i =
1; i <= n; i++)
-
{
-
cin >> a[i].num;
-
a[i].id = i;
-
}
-
for(
int i =
1; i <= m; i++)
-
{
-
cin >> q[i].l >> q[i].r >> q[i].h;
-
q[i].l++, q[i].r++;
-
q[i].id = i;
-
}
-
sort(a+
1,a+
1+n);
-
sort(q+
1,q+
1+m);
-
memset(tree,
0,
sizeof(tree));
-
int idx =
1;
-
for(
int i =
1; i <= m; i++)
-
{
-
while(q[i].h >= a[idx].num && idx <= n)
-
{
-
update(a[idx].id,
1);
-
idx++;
-
}
-
ans[q[i].id] =
getsum(q[i].r) -
getsum(q[i].l
-1);
-
}
-
printf(
"Case %d:\n",cas++);
-
for(
int i =
1; i <= m; i++)
-
printf(
"%d\n",ans[i]);
-
}
-
return
0;
-
}
2 B - Sequence II
枚举C点，那么[1 , c-1]区间内，满足i<j&&a[i]<a[j] 的个数设为x; [c,n]区间内比c大的个数设为用；根据乘法原理，x*y就是所要的，那么枚举所有的C点，累加所有的x*y;
-
#include <iostream>
-
#include <stdio.h>
-
#include <string>
-
#include <string.h>
-
#include <algorithm>
-
const
int N=
1e5+
100;
-
using
namespace std;
-
typedef
long
long ll;
-
-
int c[N],n;
//树状数组
-
int f[N],g[N];
-
int a[N];
-
-
int lowbit(int x)
-
{
-
return x&-x;
-
}
-
-
void update(int x)
-
{
-
while(x<=n)
-
{
-
c[x]+=
1;
-
x+=
lowbit(x);
-
}
-
}
-
-
int getsum(int x)
-
{
-
int ans=
0;
-
while(x>
0)
-
{
-
ans+=c[x];
-
x-=
lowbit(x);
-
}
-
return ans;
-
}
-
-
int main()
-
{
-
int T;
-
scanf(
"%d",&T);
-
while(T--)
-
{
-
scanf(
"%d",&n);
-
for(
int i=
1;i<=n;i++)
scanf(
"%d",&a[i]);
-
-
memset(c,
0,
sizeof(c));
-
for(
int i=
1;i<=n;i++)
-
{
-
f[i]=
getsum(a[i]);
-
update(a[i]);
-
}
-
-
memset(c,
0,
sizeof(c));
-
for(
int i=n;i>=
1;i--)
-
{
-
update(a[i]);
-
g[i]=n-i+
1-
getsum(a[i]);
-
}
-
-
ll ans=
0,sum=
0;
-
for(
int i=
1;i<=n;i++)
-
{
-
ans+=sum*g[i];
-
sum+=f[i];
-
}
-
printf(
"%I64d\n",ans);
-
}
-
return
0;
-
}
3 C - To the moon
涉及历史查询，一眼主席树的题目，关键的如何进行区间修改。
主席树与线段树不同之处就是 每一棵树是不能修改的，也就是不能够pushDown。那么能否一直新建节点？答案是不可以，如果用新建节点来替代pushDown操作，那么每一次都会一直新建到叶子节点，空间肯定是撑不住的。
主席树区间修一个很巧妙的方法：更新的时候和普通线段树一样，pushup 时由于没有pushDown 子树是不会更新的，所以用自己的 lazy 更新就可以了.也就是 sum[i] = sum[lson[i]] + sum[rson[i]] + lazy[i] * (r - l + 1)。查询的时候，将每一个节点的 lazy 值放在函数参数上带着，解决了pushDown的问题。
-
#include<bits/stdc++.h>
-
#define debug(x) cout << "[" << #x <<": " << (x) <<"]"<< endl
-
#define pii pair<int,int>
-
#define clr(a,b) memset((a),b,sizeof(a))
-
#define rep(i,a,b) for(int i = a;i < b;i ++)
-
#define pb push_back
-
#define MP make_pair
-
#define LL long long
-
#define ull unsigned LL
-
#define ls i << 1
-
#define rs (i << 1) + 1
-
#define fi first
-
#define se second
-
#define ptch putchar
-
#define CLR(a) while(!(a).empty()) a.pop()
-
-
using
namespace std;
-
inline LL read() {
-
LL s =
0,w =
1;
-
char ch =
getchar();
-
while(!
isdigit(ch)) {
-
if(ch ==
'-') w =
-1;
-
ch =
getchar();
-
}
-
while(
isdigit(ch))
-
s = s *
10 + ch -
'0',ch =
getchar();
-
return s * w;
-
}
-
inline void write(LL x) {
-
if(x <
0)
-
putchar(
'-'), x = -x;
-
if(x >
9)
-
write(x /
10);
-
putchar(x %
10 +
'0');
-
}
-
-
const
int maxn =
1e5 +
10;
-
const
int M = maxn *
40;
-
LL C[M],lazy[M];
-
int lson[M],rson[M];
-
int tot,T[maxn];
-
-
void build(int &i,int l,int r){
-
i = ++ tot;
-
C[i] = lazy[i] =
0;
-
if(l == r){
-
LL x =
read();
-
C[i] = x;
-
return ;
-
}
-
int mid = (l + r) >>
1;
-
build(lson[i],l,mid);
-
build(rson[i],mid +
1,r);
-
C[i] = C[lson[i]] + C[rson[i]];
-
}
-
-
void update(int l,int r,int ul,int ur,int &i,int last,LL val){
-
C[++ tot] = C[last];
-
lson[tot] = lson[last];
-
rson[tot] = rson[last];
-
lazy[tot] = lazy[last];
-
i = tot;
-
if(ul <= l && r <= ur){
-
C[i] += (r - l +
1) * val;
-
lazy[i] += val;
-
return ;
-
}
-
int mid = (l + r) >>
1;
-
if(ul <= mid)
update(l,mid,ul,ur,lson[i],lson[last],val);
-
if(ur > mid)
update(mid +
1,r,ul,ur,rson[i],rson[last],val);
-
C[i] = C[lson[i]] + C[rson[i]] + (r - l +
1) * lazy[i];
-
}
-
-
LL query(int l,int r,int ql,int qr,int i,LL add){
-
if(ql <= l && r <= qr){
-
return C[i] + add * (r - l +
1);
-
}
-
int mid = (l + r) >>
1;
-
LL ans =
0;
-
if(ql <= mid) ans +=
query(l,mid,ql,qr,lson[i],add + lazy[i]);
-
if(qr > mid) ans +=
query(mid +
1,r,ql,qr,rson[i],add + lazy[i]);
-
return ans;
-
}
-
-
int main() {
-
int n =
read(),m =
read();
-
build(T[
0],
1,n);
-
int now =
0;
-
while(m --){
-
char op;
scanf(
" %c",&op);
-
if(op ==
'C'){
-
int l =
read(),r =
read(),d =
read();
-
update(
1,n,l,r,T[now +
1],T[now],d);
-
++ now;
-
}
-
else
if(op ==
'Q'){
-
int l =
read(),r =
read();
-
write(
query(
1,n,l,r,T[now],lazy[now]));
ptch(
'\n');
-
}
-
else
if(op ==
'H'){
-
int l =
read(),r =
read(),t =
read();
-
write(
query(
1,n,l,r,T[t],lazy[t]));
ptch(
'\n');
-
}
-
else {
-
int t =
read();
-
now = t;
-
}
-
}
-
return
0;
-
}
4 D - 粟粟的书架
这题其实是分两个题来做
对于R > 1时，设计状态如下:
fi,j,k:从(1,1)到(i,j)的矩形里，大于等于k的数字的总和
gi,j,k:从(1,1)到(i,j)的矩形里，大于等于k的数字的个数
每次询问等价成4个矩形里的结果相加减，二分k，暴力算最小的那个数要多少个就行
对于R == 1时，建立一棵主席树就行了
-
#include<iostream>
-
#include<cstdio>
-
#include<queue>
-
#include<vector>
-
#include<bitset>
-
#include<algorithm>
-
#include<cstring>
-
#include<map>
-
#include<stack>
-
#include<set>
-
#include<cmath>
-
#include<ext/pb_ds/priority_queue.hpp>
-
using
namespace std;
-
-
const
int maxn =
5E5 +
50;
-
const
int T =
20;
-
const
int N =
202;
-
const
int M =
1010;
-
-
int R,C,q,cnt,f[N][N][M],g[N][N][M],root[maxn]
-
,lc[maxn*T],rc[maxn*T],c[maxn*T],t[maxn*T];
-
-
bool Judge(int r1,int c1,int r2,int c2,int k,int h)
-
{
-
return f[r2][c2][k] - f[r1
-1][c2][k] - f[r2][c1
-1][k] + f[r1
-1][c1
-1][k] >= h;
-
}
-
-
void Print(int r1,int c1,int r2,int c2,int k,int h)
-
{
-
int z = k +
1;
-
int ans = g[r2][c2][z] - g[r1
-1][c2][z] - g[r2][c1
-1][z] + g[r1
-1][c1
-1][z];
-
int res = f[r2][c2][z] - f[r1
-1][c2][z] - f[r2][c1
-1][z] + f[r1
-1][c1
-1][z];
-
res = h - res;
-
int Add = res / k;
-
if (res % k !=
0) ++Add;
-
printf(
"%d\n",ans + Add);
-
}
-
-
int Insert(int o,int l,int r,int k)
-
{
-
int ret = ++cnt;
-
c[ret] = c[o] + k;
-
t[ret] = t[o] +
1;
-
if (l == r)
return ret;
-
int mid = (l + r) >>
1;
-
if (k <= mid) rc[ret] = rc[o],lc[ret] =
Insert(lc[o],l,mid,k);
-
else lc[ret] = lc[o],rc[ret] =
Insert(rc[o],mid+
1,r,k);
-
return ret;
-
}
-
-
int Query(int o1,int o2,int l,int r,int h)
-
{
-
int tot = c[o2] - c[o1];
-
if (tot < h)
return
-1;
-
if (l == r) {
-
int ret = h / l;
-
if (h % l !=
0) ++ret;
-
return ret;
-
}
-
int ret,res,mid = (l + r) >>
1;
-
res = c[rc[o2]] - c[rc[o1]];
-
if (res >= h)
return
Query(rc[o1],rc[o2],mid+
1,r,h);
-
ret = t[rc[o2]] - t[rc[o1]];
-
return ret +
Query(lc[o1],lc[o2],l,mid,h - res);
-
}
-
-
int getint()
-
{
-
char ch =
getchar();
-
int ret =
0;
-
while (ch <
'0' ||
'9' < ch) ch =
getchar();
-
while (
'0' <= ch && ch <=
'9')
-
ret = ret*
10 + ch -
'0',ch =
getchar();
-
return ret;
-
}
-
-
int main()
-
{
-
#ifdef DMC
-
freopen(
"DMC.txt",
"r",stdin);
-
#endif
-
-
R =
getint();
-
C =
getint();
-
q =
getint();
-
if (R >
1) {
-
for (
int i =
1; i <= R; i++)
-
for (
int j =
1; j <= C; j++) {
-
int x =
getint();
-
for (
int k =
1; k <= x; k++) {
-
f[i][j][k] = f[i
-1][j][k] + f[i][j
-1][k] - f[i
-1][j
-1][k] + x;
-
g[i][j][k] = g[i
-1][j][k] + g[i][j
-1][k] - g[i
-1][j
-1][k] +
1;
-
}
-
for (
int k = x +
1; k <=
1000; k++) {
-
f[i][j][k] = f[i
-1][j][k] + f[i][j
-1][k] - f[i
-1][j
-1][k];
-
g[i][j][k] = g[i
-1][j][k] + g[i][j
-1][k] - g[i
-1][j
-1][k];
-
}
-
}
-
-
while (q--) {
-
int r1 =
getint(),c1 =
getint();
-
int r2 =
getint(),c2 =
getint();
-
int h =
getint();
-
int l =
0,r =
1001;
-
while (r - l >
1) {
-
int mid = (l + r) >>
1;
-
if (
Judge(r1,c1,r2,c2,mid,h)) l = mid;
-
else r = mid;
-
}
-
if (
Judge(r1,c1,r2,c2,r,h))
Print(r1,c1,r2,c2,r,h);
-
else
if (
Judge(r1,c1,r2,c2,l,h))
Print(r1,c1,r2,c2,l,h);
-
else
puts(
"Poor QLW");
-
}
-
}
-
else {
-
for (
int i =
1; i <= C; i++) {
-
int x =
getint();
-
root[i] =
Insert(root[i
-1],
1,
1000,x);
-
}
-
while (q--) {
-
int r1 =
getint(),c1 =
getint();
-
int r2 =
getint(),c2 =
getint();
-
int h =
getint();
-
int ans =
Query(root[c1
-1],root[c2],
1,
1000,h);
-
if (ans !=
-1)
printf(
"%d\n",ans);
-
else
puts(
"Poor QLW");
-
}
-
}
-
return
0;
-
}
5 E - 森林
动态维护树上两点间第 k 值 LCT 不能直接维护第 k 值，也很难嵌套其他数据结构，所以我们不考虑它；发现只有 加边没有删边，考虑使用主席树启发式合并 具体来说, 加边时, 把节点少的主席树合并到节点多的主席树上面，复杂度 slogs,s 为 小主席树的大小, 同时动态更新父节点的倍增数组，复杂度也是 slogs 的 查询时, 进入两个点以及它们的 lca 和 lca 的爹的主席树中上上下下加加减减
-
#include <cstdio>
-
#include <cstring>
-
#include <algorithm>
-
#define ls ch[now][0]
-
#define rs ch[now][1]
-
#define ols ch[las][0]
-
#define ors ch[las][1]
-
const
int N=
3e5+
10;
-
int ch[N*
-
30][
2],sum[N*
-
30],tot;
-
int f[N][
20],dep[N],n,m,n_,t,tmp,siz[N],root[N],a[N],b[N],testcase;
-
void updata(int now){sum[now]=sum[ls]+sum[rs];}
-
int rebuild(int las,int l,int r,int pos)
-
{
-
int now=++tot;
-
if(l==r) {sum[now]+=sum[las]+
1;
return now;}
-
int mid=l+r>>
1;
-
if(pos<=mid)
-
{
-
ls=
rebuild(ols,l,mid,pos);
-
rs=ors;
-
}
-
else
-
{
-
ls=ols;
-
rs=
rebuild(ors,mid+
1,r,pos);
-
}
-
updata(now);
-
return now;
-
}
-
int head[N],to[N<<
1],Next[N<<
1],cnt;
-
void add(int u,int v)
-
{
-
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
-
}
-
int dfs(int now,int fa)
-
12
-
{
-
int s=
1;
-
root[now]=
rebuild(root[fa],
1,n,b[now]);
-
f[now][
0]=fa;
-
dep[now]=dep[fa]+
1;
-
for(
int i=
1;i<=
18;i++)
-
f[now][i]=f[f[now][i−
1]][i−
1];
-
for(
int i=head[now];i;i=Next[i])
-
if(to[i]!=fa)
-
s+=
dfs(to[i],now);
-
return s;
-
}
-
void swap(int &x,int &y){tmp=x,x=y,y=tmp;}
-
int rt(int now)
-
{
-
for(
int i=
18;~i;i−−)
-
if(f[now][i])
-
now=f[now][i];
-
return now;
-
}
-
void Merge(int x,int y)
-
{
-
int rx=
rt(x),ry=
rt(y);
-
if(siz[rx]<siz[ry])
swap(rx,ry),
swap(x,y);
-
add(x,y),
add(y,x);
-
siz[rx]+=
dfs(y,x);
-
}
-
int LCA(int x,int y)
-
{
-
if(dep[x]<dep[y])
swap(x,y);
-
for(
int i=
18;~i;i−−)
-
if(dep[f[x][i]]>=dep[y])
-
x=f[x][i];
-
if(x==y)
return x;
-
for(
int i=
18;~i;i−−)
-
if(f[x][i]!=f[y][i])
-
x=f[x][i],y=f[y][i];
-
return f[x][
0];
-
}
-
int query(int rt1,int rt2,int rt3,int rt4,int l,int r,int k)
-
{
-
if(l==r)
return a[l];
-
int mid=l+r>>
1,s=sum[ch[rt1][
0]]+sum[ch[rt2][
0]]−sum[ch[rt3][
0]]−sum[ch[rt4
-
][
0]];
-
if(s>=k)
return
query(ch[rt1][
0],ch[rt2][
0],ch[rt3][
0],ch[rt4][
0],l,mid,k);
-
else
return
query(ch[rt1][
1],ch[rt2][
1],ch[rt3][
1],ch[rt4][
1],mid+
1,r,k−s);
-
}
-
int main()
-
-
{
-
scanf(
"%d",&testcase);
-
tot=
0,cnt=
0;
-
scanf(
"%d%d%d",&n_,&m,&t);
-
for(
int i=
1;i<=n_;i++)
scanf(
"%d",a+i),b[i]=a[i];
-
std::
sort(a+
1,a+
1+n_);
-
n=std::
unique(a+
1,a+
1+n_)−a−
1;
-
for(
int i=
1;i<=n_;i++) b[i]=std::
lower_bound(a+
1,a+
1+n,b[i])−a;
-
for(
int u,v,i=
1;i<=m;i++)
-
{
-
scanf(
"%d%d",&u,&v);
-
add(u,v),
add(v,u);
-
}
-
for(
int i=
1;i<=n_;i++)
-
if(!f[i][
0])
-
siz[i]=
dfs(i,
0);
-
int lastans=
0;
char op[
4];
-
for(
int u,v,k,i=
1;i<=t;i++)
-
{
-
scanf(
"%s%d%d",op,&u,&v);
-
u^=lastans,v^=lastans;
-
if(op[
0]==
'Q')
-
{
-
scanf(
"%d",&k);
-
k^=lastans;
int lca=
LCA(u,v);
-
printf(
"%d\n",lastans=
query(root[u],root[v],root[lca],root[f[lca][
0]],
1,n,
-
k));
-
}
-
else
-
Merge(u,v);
-
}
-
return
0;
-
}
转载：https://blog.csdn.net/m0_61735576/article/details/128553874
查看评论