首页 > 其他分享 >题解 链表 (chain)

题解 链表 (chain)

时间:2023-07-25 11:24:32浏览次数:50  
标签:连通 chain int 题解 sum long 链表 read ge

题目链接

首先考虑没有修改怎么做。

两种做法。

想到询问的形式为保留 \(\ge k\) 的连通块个数,那么先将全部数字按照权值排序,然后从后往前做一遍并查集,并同时统计连通块的数量,在询问时只需二分找到第一个 \(\ge k\) 的位置,将这个位置的答案输出即可。注意考虑答案为 \(0\) 的情况。

但是显然,上面的做法是很难拓展为有修改的情况的,所以这是就要提到另一种做法。

考虑对于一个 \(k\),哪些情况下会产生新的连通块,显然当 \(a_{i+1}\ge k\) 且 \(a_{i}< k\) 时,在 \(i\) 和 \(i+1\) 之间会断开,产生新的连通块。如果考虑对于一个答案,有多少种这样的情况,由于 \(k\) 会变,所以我们不得不在 \(O(n)\) 遍历一遍,总时间复杂度是 \(O(nm)\)。

考虑对于一种情况,会对多少种答案产生贡献,显然,若 \(a_{i}<a_{i+1}\),那么,当 \(k\in [a_{i}+1,a_{i+1}]\),该种情况都会对所有 \(k\) 产生 \(1\) 的贡献。询问时将对应的 \(ans_k\) 输出即可。这是一个区间加,单点查的操作,前缀和+差分即可。

如果加上修改操作,那么对于一个位置上的 \(x\),将其换成 \(x'\),只需将之前的贡献消除,将新的贡献加上即可。区间修单点查,容易想到树状数组。

点击查看代码
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
LL read() {
    LL sum=0,flag=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
    while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
    return sum*flag;
}

const int N=5e5+10,M=5e5;
int n,m;
int tr[N];
int a[N];

int lowbit(int x) {
    return x&(-x);
}

void change(int nd,int x) {
    for(int i=nd;i<=M;i+=lowbit(i)) tr[i]+=x;
}

int query(int nd) {
    int sum=0;
    for(int i=nd;i>=1;i-=lowbit(i)) sum+=tr[i];
    return sum;
}

void add(int l,int r,int x) {
    change(l,x);
    change(r+1,-x);
}

int main() {
    n=read(); m=read();
    for(int i=1;i<=n;i++) {
        a[i]=read();
        if(a[i-1]<a[i]) add(a[i-1]+1,a[i],1);
    }
    int lst=0;
    while(m--) {
        string opt; int x,y;
        cin>>opt;
        if(opt=="Q") {
            x=read(); x^=lst;
            lst=query(x);
            cout<<lst<<'\n';
        }
        else {
            x=read(); y=read();
            x^=lst; y^=lst;
            if(a[x-1]<a[x]) add(a[x-1]+1,a[x],-1);
            if(a[x]<a[x+1]) add(a[x]+1,a[x+1],-1);
            a[x]=y;
            if(a[x-1]<a[x]) add(a[x-1]+1,a[x],1);
            if(a[x]<a[x+1]) add(a[x]+1,a[x+1],1);
        }
    }


    return 0;
}

标签:连通,chain,int,题解,sum,long,链表,read,ge
From: https://www.cnblogs.com/zhangyuzhe/p/17579219.html

相关文章

  • 【大联盟】20230713 T1 方向矩阵(rect) 题解 CF1666A 【Admissible Map】
    题目描述here。题解赛时得分:60/100。想到了正解,但调不出来,就改写暴力了。。。首先,我们把问题转化成每个点都入度为\(1\)。我们考虑合法子串只有两种形式:注意到U和D,要么同时出现,要么同时不出现,因为如果存在U,就说明U所在这一行得到度数减少了,一定需要上一行D来弥补......
  • 运势计算:以双向链表实现: 解读运势
    1解读运势我们已经做了些什么?这一小节我们将能看到我们做了一些什么事情,还记得第一小节的链表查询函数吗?没错就是display,在第二小节中,我们将每次的爻变记录和爻值存入了链表,现在我们实现它以显示爻变的过程。///显示并返回链表的值func(this*dlist)display()[]int{......
  • luogu P3203 [HNOI2010] 弹飞绵羊 题解
    题目传送门:P3203[HNOI2010]弹飞绵羊题意\(n\)个数,满足\(i<a_i≤N+1\),\(m\)次下面两种操作修改一个数\(a_i\)从\(x\)开始跳,\(x=a_x\),几次能够跳出序列\(n\leq2*10^5,m<10^5\)分析数据范围比较大,单纯搜索模拟肯定会T,那么考虑每次让他跳一段就......
  • 题解 P7971【[KSN2021] Colouring Balls】
    postedon2022-10-0819:07:28|under题解|sourceproblem交互库有一个长为\(n\)的颜色序列,你可以询问区间\([l,r]\)中有多少种颜色,最后还原交互库手中的序列,只需要保持相对顺序不变。\(n\leq10^3\),最多询问次数\(Q=2000\)或\(Q=10^4\)。solution令\(C\)为\([1......
  • CF1051G Distinctification题解
    link首先可以发现,题目给定的两种操作为我们提供了“反悔机制”,所以有:结论\(1\):即任何一个可以到达的局面都能到达最优解。利用这个结论,首先我们先去重。继续提炼性质,与相差不到\(1\)的数为基准\(+1\)与\(-1\)操作,将这个数的变化范围限制在了一个区间,并且这个区间的数能......
  • 题解 Codeforces Round 887 (Div 1+Div 2) / CF1853AB,CF1852ABCD
    下大分!悲!Div1只过了1A!!!但还是补完整场Div2吧。A.Desortinghttps://codeforces.com/problemset/problem/1853/Aproblem用操作:\([1,i]++,[i+1,n]--\),使得数组不单调不降,求最小操作次数。\(n\leq10^5\)。solution操作等同于在差分数组上选出\(i\),做\(c_1:=c_1+1,c_i:......
  • UOJ #284. 快乐游戏鸡题解(长链剖分+单调栈合并)
    UOJ#284.快乐游戏鸡题解(长链剖分+单调栈合并)题面一番战斗之后,程序猿被计算鸡们赶走了。随着垫子计算鸡一声令下:“追!”,于是计算鸡村全村上下开始乘胜追击。计算鸡们希望在新的一年到来之际给程序猿以重创,出掉这一年的恶气。可是程序猿一追就走,一走就跑,一跑就无影无踪。计算鸡......
  • LeetCode 热题 100 之 21. 合并两个有序链表
    题目将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例2:输入:l1=[],l2=[]输出:[]示例3:输入:l1=[],l2=[0]输出:[0]提示:两个链表的节点数目范围是[......
  • 洛谷CF1738C题解
    好一道博弈论水题题目传送门更好的食用体验题目大意:给定长度为$n$的数列$a_1,a_2,\dots,a_n$,两名玩家Alice、Bob依次以最优策略从数列中取走一个数,Alice先取,直至为空博弈结束。若Alice取走的所有数之和为偶,Alice胜利;若Alice取走的所有数之和为奇,Bob胜利......
  • 【题解】Imbalanced Arrays - Codeforces 1852B
    出处:CodeforcesRound887链接:https://codeforces.com/problemset/problem/1852/B题目大意:给定一个包含\(n\)个非负整数的频次序列\(f\)。构造任意一个等长的整数序列\(b\),要求①\(b\in[-n,n]\)but$b\neq0$②\(b\)中不存在相反数③对于每个坐标\(i\)......