一个简单的数组套线段树
2024-06-09 12:21:37
发布于:上海
7阅读
0回复
0点赞
定睛一看,这题就是一道数据结构题。
题意简述
给定一个矩阵,要求你资瓷一种修改和一种查询操作:
- 将矩阵 全部作标记。
- 询问 被作了几次标记,最后一次标记是什么时候做的。
我们自然想到了数组套线段树。对于每一行,有一颗线段树对应它的每一列。每一个节点都要记录被标记的次数和最后被标记的时间。修改时,我们为对应行的线段树进行区间标记。查询时,我们返回对应行列的节点编号,得到这个点的被标记的次数和最后被标记的时间。经过一波计算,我们发现单次修改的时间复杂度为 ,单次查询的时间复杂度为 。若 与 同数量级(题目未标明),则总时间复杂度为 ,相比一般模拟的 优。当然这题数据过水,你怎么写都能AC。
AC Code~ 不要只看这里啊。
#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 100
#define m(l,r) ((l+r)>>1)
#define ls(k) (k<<1)
#define rs(k) ((k<<1)|1)
int n,m,x,y;
struct segment_tree{ // 内层线段树
struct node{
int l,r;
int dat,tag,lun;
}t[4*MAXN+5];
void build(int p, int l, int r){
t[p].l=l;
t[p].r=r;
t[p].tag=t[p].dat=0;
if(l==r)return;
int mid=m(l,r);
build(ls(p),l,mid);
build(rs(p),mid+1,r);
t[p].dat=t[ls(p)].dat+t[rs(p)].dat;
}
inline void down(int p){
if(t[p].tag){
t[ls(p)].dat+=t[p].tag;
t[ls(p)].tag+=t[p].tag;
t[ls(p)].lun=t[rs(p)].lun=t[p].lun;
t[rs(p)].dat+=t[p].tag;
t[rs(p)].tag+=t[p].tag;
t[p].tag=0;
}
}
void change(int p,int x,int y,int lun){
if(x<=t[p].l && y>=t[p].r){
t[p].dat+=1;
t[p].tag+=1;
t[p].lun=lun;
return;
}
down(p);
int mid=m(t[p].l,t[p].r);
if(x<=mid) change(ls(p),x,y,lun);
if(y>mid) change(rs(p),x,y,lun);
t[p].dat=t[ls(p)].dat+t[rs(p)].dat;
}
int ask(int p,int x){
if(x==t[p].l && x==t[p].r) return p;
down(p);
long long mid=m(t[p].l,t[p].r);
if(x<=mid) return ask(ls(p),x);
else return ask(rs(p),x);
}
}trees[105]; // n颗
inline int read(){ // 非负读
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x;
}
inline void write(int x){ // 非负写
if(x>9) write(x/10);
putchar((x%10)^48);
}
int main(){
n=read(),m=read(),x=read(),y=read();
for(int i=1; i<=n; i++){
trees[i].build(1,1,m);
}
for(int j=1; j<=x; j++){
int x,y,a,b;
x=read(),y=read(),a=read(),b=read();
for(int i=x; i<=a; i++){
trees[i].change(1,y,b,j);
}
}
while(y--){
int x,y;
x=read(),y=read();
int idx=trees[x].ask(1,y);
if(trees[x].t[idx].dat){
putchar('Y');
putchar(32);
write(trees[x].t[idx].dat);
putchar(32);
write(trees[x].t[idx].lun);
putchar(10);
}else{
putchar('N');
putchar(10);
}
}
return 0;
}
课后作业:试着使用线段树套线段树(或树状数组)(可以参考P3380 【模板】树套树)进一步优化时间复杂度,令单次修改的时间复杂度为 ,单次查询的时间复杂度为 ,总时间复杂度为 。哈哈我真是无聊@_@
这里空空如也
有帮助,赞一个