国庆前几天把团体训练里的每日训练写完,加上每天一场edu,后几天刷的洛谷数据结构。
个人感觉比较有意义的题目:
C. Not Equal on a Segment
题目大意:给出一个长度为n的数列,然后给出m次询问,每次询问的格式是l,r,x,要求我们输出任意一个在区间[l,r]内值不等于x的下标
这题目好像是可以直接递推的写,只需要记录连续相同的数第一次出现位置,依次递推。
但是我用的ST表+二分写的。
实现思路:对于每一个查询,用ST表查出该区间最大值与最小值,如果最大值和最小值相等并且等于x,输出-1;
否则,首先预处理出每个值的所在下标,我用的set存每个值的下标,然后二分查询两个最值中不等于x的值在[l,r]区间内的下标。
代码:
// /l、 //(゚、 。 7 // l、 ~ヽ // じしf_, )ノ // 不要放弃!猫猫会为你加油! #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <set> #define endl '\n' using namespace std; const int N = 2e5+10 , M = 1e6+10 ; int n,m; int fi[N][20],fx[N][20],lg[N]; set<int> s[M]; void init() { for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; for(int j=1;j<=18;j++) { for(int i=1;i+(1<<j)-1<=n;i++) { fi[i][j]=min(fi[i][j-1],fi[i+(1<<(j-1))][j-1]); fx[i][j]=max(fx[i][j-1],fx[i+(1<<(j-1))][j-1]); } } } int query_min(int l,int r) { int k = lg[r-l+1]; return min(fi[l][k],fi[r-(1<<k)+1][k]); } int query_max(int l,int r) { int k = lg[r-l+1]; return max(fx[l][k],fx[r-(1<<k)+1][k]); } void solve() { cin >> n >> m; memset(fi , M , sizeof fi); for(int i=1;i<=n;i++) { int x; cin >> x; fi[i][0]=x , fx[i][0]=x; s[x].insert(i); } init(); while(m--) { int l,r,x; cin >> l >> r >> x; int a = query_min(l,r) , b = query_max(l,r); if(a==b && b==x) cout << -1 << endl; else { int w; if(a==x) w=b; else w=a; int t = *s[w].lower_bound(l); cout << t << endl; } } } signed main() { ios::sync_with_stdio(0); cin.tie(0) , cout.tie(0); int T = 1; // cin >> T ; while(T--) solve(); return 0; }
C:Foe Pairs
题意:给定一些线段,请计算有多少个区间满足没有一条线段被完整包含。
思考:对于每个左端点枚举从该点往后走,最远能走到哪,首先初始化所有点能到的最远距离f[i]=n
题解:先处理单点再前缀扫一遍:令f[i]表示 i 位置往左往右走到最远的地方是哪,对于所有区间[l,r],左端点在 l 的线段f[l]=min(f[l],r-1);最后作一个后缀最小值f[i]=min(f[i],f[i+1]),表示每个点能走到的最远距离即可。
代码:
// /l、 //(゚、 。 7 // l、 ~ヽ // じしf_, )ノ // 不要放弃!猫猫会为你加油! #include <iostream> #include <algorithm> #include <vector> #include <map> #define endl '\n' #define int long long using namespace std; const int N = 3e5+10 , M = 1e6+10; int n,m; int k[N],f[N]; void solve() { cin >> n >> m; map<int , int> mp; for(int i=1;i<=n;i++) { cin >> k[i]; mp[k[i]]=i; f[i]=n; } for(int i=1;i<=m;i++) { int l,r; cin >> l >> r; l = mp[l] , r = mp[r]; if(l>r) swap(l,r); f[l]=min(f[l],r-1); } for(int i=n-1;i>=1;i--) f[i]=min(f[i],f[i+1]); int ans=0; for(int i=1;i<=n;i++) ans+=f[i]-i+1; cout << ans << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0) , cout.tie(0); int T = 1; // cin >> T ; while(T--) solve(); return 0; }
C. Nested Segments
题意:在一条直线上有 n 条线段。有些线段的两端不重合。求每条线段包含的线段数。
思考:题意挺简单的,先开始感觉是贪心,结果一写发现不对,不是贪心,根本贪不了;但是线段覆盖这种问题想半天我也没想到有啥写法,看题解发现树状数组居然能写(可能是我脑子宕机了,真没想到)
题解:我们将线段按照左端点从大到小排序,然后树状数组对每条线段的右端点进行修改和查询(数据范围很大,要先离散化)。这样我们就能保证,在查询点之前的线段的左右端点一定在当前线段左右端点之间。
代码:
const int N = 4e5+10 , M = 1e6+10 ; int n , cnt=1; int tr[N] , ans[N]; struct node{ int x,y,id; }k[N]; bool cmp1(node a,node b) { if(a.x == b.x) return a.y < b.y; return a.x > b.x; } bool cmp2(node a ,node b) { return a.id < b.id; } int lowbit(int x) { return x & -x; } void add(int x) { for(int i=x;i<=cnt;i+=lowbit(i)) tr[i]++; } int query(int x) { int res=0; for(int i=x;i;i-=lowbit(i)) res+=tr[i]; return res; } void solve() { cin >> n; map<int , int> mp; for(int i=1;i<=n;i++) { cin >> k[i].x >> k[i].y; mp[k[i].x]=1 , mp[k[i].y]=1 , k[i].id=i; } for(auto & [a,b] : mp) mp[a]=cnt , cnt++; sort(k+1,k+n+1,cmp1); for(int i=1;i<=n;i++) { int y = mp[k[i].y]; ans[k[i].id]=query(y); add(y); } sort(k+1,k+n+1,cmp2); for(int i=1;i<=n;i++) cout << ans[i] << endl; }
洛谷复习的和刷的一点数据结构,这里都是一些简单的数据结构,并查集,ST表,树状数组啥的,后续会继续刷线段树的题。
然后10月4日下午,令人悲伤的事情发生了?,突然高烧至39度,头昏头痛,所以最后两天没干啥,在寝室呆了两天休息 。