5 条题解

  • 4
    @ 2026-8-22 15:59:18

    观察题目，要我们考虑在不同海平面的情况下讨论“岛屿”的个数

    因为如果按正常顺序一会加一会减很麻烦，所以我们很容易就想到给询问按x从小到大排序，具有单调性。 同时h也排序，记录id。

    之后枚举每个询问，改变那些要变成0的h，此时，我们要弄清楚它们分别属于那些岛屿，所以联想到开集合L和R，记录每个岛屿的l和r。

    此时用二分找到对应的l与r，然后看id在岛屿中具体处于什么位置，对L与R集合做出具体改变（详见代码）

    最后解决当前询问的l和r，注意到在L和R中的l[i]与r[i]是一一对应的，所以查询l和r分别在R与L集合中处于什么位置，注意到集合set实现此操作需要O(N)的时间复杂度，所以考虑pb_ds，用O(logN)实现此操作，最终将两位置相减得到最终答案。

    #include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int N=2e5+10;
struct node
{
	int h,id;
}a[N];
bool cmp(node A,node B)
{
	return A.h<B.h;
}
int h[N];
struct node1
{
	int l,r,x,id;
}t[N];
bool cmp1(node1 A,node1 B)
{
	return A.x<B.x;
}
int ans[N];
ordered_set L,R;//pb_ds
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&h[i]);
		a[i].h=h[i];
		a[i].id=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(h[i]&&!h[i-1])
		{
			L.insert(i);
		}
		if(h[i]&&!h[i+1])
		{
			R.insert(i);
		}
	}//注意此处初始化不能只塞入(1,n)，要防止某个h[i]=0同时询问的x为0的情况 
	sort(a+1,a+n+1,cmp);//按h排序 
	sort(h+1,h+n+1);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d",&t[i].l,&t[i].r,&t[i].x);	
		t[i].id=i;	
	}
	sort(t+1,t+q+1,cmp1);//按x排序 
	int last=0;//记录之前最后改变为0的id 
	for(int i=1;i<=q;i++)
	{
		int x=t[i].x;
		int p=upper_bound(h+1,h+n+1,x)-h-1;
		if(p>last)
		{
			for(int j=last+1;j<=p;j++)//O(NlogN)的改变 
			{
				if(h[j]==0)
				{
					continue;
				}
				int id=a[j].id;
				auto ll=L.upper_bound(id);
				ll--;
				auto rr=R.lower_bound(id);
				int l=*ll;
				int r=*rr;
				if(l==r)
				{
					L.erase(l);
					R.erase(r);
				}
				else if(l==id)
				{
					L.erase(l);
					L.insert(l+1);
				}
				else if(r==id)
				{
					R.erase(r);
					R.insert(r-1);
				}
				else
				{
					L.insert(id+1);
					R.insert(id-1);
				}//具体的处理操作 
			}
		}
		last=p;
		int l=t[i].l,r=t[i].r;
		int ll=R.order_of_key(l)+1,rr=L.order_of_key(r+1);
		ans[t[i].id]=rr-ll+1;//记录原id的ans 
	}
	for(int i=1;i<=q;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}//注：此代码纯乱搞，无算法
    • 2
      @ 2026-8-24 16:19:21

      思路

      很容易发现如果按照正常的顺序计算问题，海平面上上下下，不是很方便计算，因此考虑进行排序使得海平面单调下降，方便计算。如此一来，一个山峰露出来我们需要将他标记一下，顺便计算他对答案的贡献。单点修改，区间查询，考虑使用线段树维护。

      在一个树节点中维护三个变量：cnt,isl,isrcnt,isl,isr分别表示这一区间内岛屿的数量，区间左右端点是否露出来了，具体的转移及查询操作见代码。

      AC代码

      #include<bits/stdc++.h>
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
using namespace std;
const int N=2e5+10;
struct node{int l,r,x,id;}q[N];//存储询问 
int ans[N];
struct nod{int x,id;}a[N];//存储山峰 
struct trnode{int l,r,cnt;bool isl,isr;}tr[N<<2];//存储查询 
void pu(int p)
{
	tr[p].cnt=tr[lc(p)].cnt+tr[rc(p)].cnt-(tr[lc(p)].isr&&tr[rc(p)].isl);//记得减去中间重复的情况 
	tr[p].isl=tr[lc(p)].isl;tr[p].isr=tr[rc(p)].isr;
}
void build(int p,int l,int r)
{
	tr[p].l=l,tr[p].r=r;
	if(l==r)return ;
	int mid=l+r>>1;
	build(lc(p),l,mid);build(rc(p),mid+1,r);
}
void change(int p,int x)
{
	if(tr[p].r<x||x<tr[p].l)return ;
	if(tr[p].l==tr[p].r)
	{
		tr[p].cnt=tr[p].isl=tr[p].isr=1;//就是这个岛 
		return ;
	}
	change(lc(p),x);
	change(rc(p),x);
	pu(p);
}
trnode query(int p,int l,int r)//实在不想再开新的结构体了，用trnode将就一下 
{
	if(tr[p].r<l||r<tr[p].l)return {0,0,0,0,0};
	if(l<=tr[p].l&&tr[p].r<=r)return {0,0,tr[p].cnt,tr[p].isl,tr[p].isr};
	trnode n1=query(lc(p),l,r),n2=query(rc(p),l,r);
	return {0,0,n1.cnt+n2.cnt-(n1.isr&&n2.isl),n1.isl,n2.isr};
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i].x),a[i].id=i;
	sort(a+1,a+n+1,[](nod n1,nod n2){return n1.x<n2.x;});//对山峰进行排序，方便后续计算 
	for(int i=1;i<=m;i++)scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x),q[i].id=i;
	sort(q+1,q+m+1,[](node n1,node n2){return n1.x>n2.x;});
	build(1,1,n);//千万别忘了建树！！！ 
	for(int i=1,j=n;i<=m;i++)
	{
		while(j>=1&&a[j].x>q[i].x)change(1,a[j].id),j--;//双指针找寻那些山峰该露出来 
		ans[q[i].id]=query(1,q[i].l,q[i].r).cnt;
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;//完结撒花~ 
}
      • 1
        @ 2026-8-27 11:28:33

        比较接近线段树模板吧，除了 queryquery 函数有小小的改动。

        #include<bits/stdc++.h>
using namespace std;
#define lp (p<<1)
#define rp (p<<1|1)
const int N=2e5+10;
struct trnd{int l,r,cnt;bool ls,rs;}tr[N<<2];
struct nd{int pos,h;}a[N];
struct qnd{int id,l,r,x,ans;}ask[N];
bool cmp1(nd n1,nd n2){return n1.h>n2.h;}
bool cmp2(qnd n1,qnd n2){return n1.x>n2.x;}
bool cmp3(qnd n1,qnd n2){return n1.id<n2.id;}
void pushup(int p)
{
	tr[p].cnt=tr[lp].cnt+tr[rp].cnt-(tr[lp].rs&&tr[rp].ls);
	tr[p].ls=tr[lp].ls;tr[p].rs=tr[rp].rs;
}
void bt(int p,int l,int r)
{
	tr[p]={l,r,0,0,0};
	if(l==r)return;
	int mid=(l+r)>>1;
	bt(lp,l,mid);
	bt(rp,mid+1,r);
	pushup(p);
}
void change(int p,int x)
{
	if(x<tr[p].l||tr[p].r<x)return;
	if(tr[p].l==tr[p].r)
	{
		tr[p].cnt=tr[p].ls=tr[p].rs=1;
		return;
	}
	change(lp,x);
	change(rp,x);
	pushup(p);
}
int query(int p,int l,int r)
{
	if(r<tr[p].l||tr[p].r<l)return -1;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].cnt;
	int lcnt=query(lp,l,r),rcnt=query(rp,l,r);
	if(lcnt!=-1&&rcnt!=-1)return lcnt+rcnt-(tr[lp].rs&&tr[rp].ls);
	if(lcnt==-1)lcnt=0;
	if(rcnt==-1)rcnt=0;
	return lcnt+rcnt;
}
int main()
{
	int n,q;scanf("%d%d",&n,&q);
	for(int i=1,h;i<=n;i++)
	{
		scanf("%d",&h);
		a[i]={i,h};
	}
	sort(a+1,a+n+1,cmp1);
	for(int i=1,l,r,x;i<=q;i++)
	{
		scanf("%d%d%d",&l,&r,&x);
		ask[i]={i,l,r,x,0};
	}
	sort(ask+1,ask+q+1,cmp2);
	int id=1;bt(1,1,n);
	for(int i=1;i<=q;i++)
	{
		while(id<=n&&a[id].h>ask[i].x)change(1,a[id].pos),id++;
		ask[i].ans=query(1,ask[i].l,ask[i].r);
	}
	sort(ask+1,ask+q+1,cmp3);
	for(int i=1;i<=q;i++)printf("%d\n",ask[i].ans);
	return 0;
}
        • 1
          @ 2026-4-27 15:27:05

          解法

          一组询问

          先考虑一个简化版的情况，如果只有一组询问怎么处理。

          那不直接打暴力

          可以考虑一个常见的技巧：每个位置赋一个颜色 cic_i，满足：

          $$c_i=\begin{cases} 1 & h_i>x\\ 0 & h_i\leq x \end{cases}$$

          这样我们就把原来的序列变成了一个 01 串。

          问题就变成了 01 串上给定区间 [l,r][l, r] 中连续的 11 的区间的个数。

          多组询问

          有个显然的结论：如果 xix_i 单调下降，则生成的 01 串中只会有 00 变成 11。

          在这种情况下问题就变成了单点修改，区间查询连续的 11 的区间的个数。

          直接线段树。解决。

          所以做法就是先将询问离线，按 xix_i 从大到小排序。

          每次先加入当前高度下新加入的节点， 然后查询 [li,ri][l_i, r_i] 间的连续的 11 的区间的个数。

          每次新加入的节点可以用桶预先统计好。

          Code

          #include<bits/stdc++.h>
using namespace std;
#define maxn 200005

struct SegT
{
    struct node
    {
        int l=0, r=0, ans=0;
        node operator+(node b) {return {l, b.r, ans+b.ans-(r&&r==b.l)};}
        void operator=(int b) {l=r=ans=b;}
    }tr[maxn<<2];

    #define lc   (x<<1)
    #define rc   (x<<1|1)
    #define mid  ((l+r)>>1)
    #define lson lc, l, mid
    #define rson rc, mid+1, r
    #define rt   1, 1, n

    void push_up(int x) {tr[x]=tr[lc]+tr[rc];}

    void modify(int x, int l, int r, int p)
    {
        if(l==r) return tr[x]=1;
        if(p<=mid) modify(lson, p);
        if(p>mid)  modify(rson, p);
        push_up(x);
    }

    node query(int x, int l, int r, int L, int R)
    {
        if(L<=l&&r<=R) return tr[x];
        if(R<=mid) return query(lson, L, R);
        if(L>mid)  return query(rson, L, R);
        return query(lson, L, R)+query(rson, L, R);
    }
}tr; // 线段树部分

vector<tuple<int, int, int, int>> qrs; // 储存离线询问
vector<int> adds[maxn] /*存储每次新加入的节点*/, hgt;
int lis[maxn], ans[maxn];

int main()
{
    int n, q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>lis[i];
    for(int i=1, l, r, x;i<=q;i++)
        cin>>l>>r>>x, 
        qrs.emplace_back(x, l, r, i), 
        hgt.emplace_back(x);
    sort(qrs.begin(), qrs.end(), greater());
    sort(hgt.begin(), hgt.end(), greater());
    for(int i=1;i<=n;i++) 
        adds[upper_bound(hgt.begin(), hgt.end(), lis[i], greater())-hgt.begin()+1].emplace_back(i); // 向桶内添加节点
    int cnt=1;
    for(auto [h, l, r, i]:qrs)
    {
        for(auto v:adds[cnt++]) tr.modify(rt, v); 
        ans[i]=tr.query(rt, l, r).ans; // 先改再查
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
}
          • 0
            @ 2026-5-17 18:42:33 
            #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,a[200010],vis[200010];
int lowbit(int x){
	return x&(-x);
}
struct NN{
	int v,x;
}b[200010];
bool cmpb(NN a,NN b){
	return a.v<b.v;
}
struct N{
	int tr[200010];
	void add(int x,int v){
		for(int i=x;i<=n;i+=lowbit(i)){
			tr[i]+=v; 
		}
	}
	int find(int x){
		int ans=0;
		for(int i=x;i;i-=lowbit(i)){
			ans+=tr[i]; 
		} 
		return ans;
	}
}tr,tr2;
struct Q{
	int l,r,x,id;
}c[200010];
bool cmp(Q a,Q b){
	return a.x<b.x;
}
int ans[200010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	int la=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]={a[i],i};
		if(a[i]){
			if(!la){
				tr.add(i,1);
			}
			la=1;
		}
		else{
			if(la)tr2.add(i-1,1);
			la=0;
		}
	}
	if(la)tr2.add(n,1);
	sort(b+1,b+1+n,cmpb);
	for(int i=1;i<=q;i++){
		cin>>c[i].l>>c[i].r>>c[i].x;
		c[i].id=i;
	}
	sort(c+1,c+1+q,cmp);
	int x=1;
	while(x<=n&&!b[x].v){
		vis[b[x].x]=1;x++;
	}
	for(int i=1;i<=q;i++){
		while(x<=n&&b[x].v<=c[i].x){
			int p=b[x].x;
			if(p==1){
				if(vis[p+1]){
					tr.add(p,-1);
					tr2.add(p,-1);
				}
				else{
					tr.add(p,-1);
					tr.add(p+1,1);
				}
			}
			else if(p==n){
				if(vis[p-1]){
					tr.add(p,-1);
					tr2.add(p,-1);
				}
				else{
					tr2.add(p,-1);
					tr2.add(p-1,1);
				}
			}
			else{
				if(vis[p-1]&&vis[p+1]){
					tr.add(p,-1);
					tr2.add(p,-1);
				}
				else if(vis[p-1]){
					tr.add(p,-1);
					tr.add(p+1,1);
				}
				else if(vis[p+1]){
					tr2.add(p,-1);
					tr2.add(p-1,1);
				}
				else{
					tr.add(p+1,1);
					tr2.add(p-1,1); 
				}
			}
			vis[p]=1;
			x++;
		}
		ans[c[i].id]=tr.find(c[i].r)-tr2.find(c[i].l-1);
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}
            • 1

            [COCI 2023/2024 #2] Zatopljenje

            信息

            ID
            7309
            时间
            2000ms
            内存
            512MiB
            难度
            6
            标签
            递交数
            47
            已通过
            15
            上传者
            1. Language
            2. 兼容模式
            3. 主题
            3. Worker 0, 10ms
            4. Powered by Hydro v5.0.1 Community