A.Worms

题意：有n堆蚯蚓每堆数量为a[i]，所有蚯蚓按堆的顺序连续编号，问第q[i]只的堆编号； 思路：计算前缀和sum[i]表示前i堆蚯蚓的总数对于每个q，找到最小的i使得sum[i]>= q，这个i就是答案

#include<bits/stdc++.h>
using namespace std;
long long s[100010];
int main(){
	int n,m;
	cin>>n;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		if(i==0)s[i]=x;
		else s[i]=s[i-1]+x;
	}
	cin>>m;
	for(int i=0;i<m;i++){
		int y;
		cin>>y;
		int l=0,r=n-1,p=0;
		while(l<=r){
			int z=l+(r-l)/2;
			if(s[z]>=y){
				r=z-1;
				p=z;
			}
			else{
				l=z+1;
			}
		}
		cout<<p+1<<"\n";
	}
	return 0;
}

B.Queries about less or equal elements https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a548de1efbe3c287b0152c7/problem/CF600B?lang=zh 题意：给定两个数组a和b对于b中的每个元素b[j]，统计a中有多少个元素<=b[j]。 思路：将数组a从小到大排序对于每个b[j]，在排序后的a中二分查找最后一个≤b[j]的位置该位置+1就是答案

#include<bits/stdc++.h>
using namespace std;
long long a[2000010];
int main(){
	long long n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	for(int i=1;i<=m;i++){
		long long b;
		cin>>b;
		long long l=0,r=n-1,p=0;
		while(l<=r){
			long long z=l+(r-l)/2;
			if(a[z]<=b){
				p=z+1;
				l=z+1;
			}
			else{
				r=z-1;
			}
		}
		cout<<p<<" ";
	}
	return 0;
}

C.Producing Snow https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a548de1efbe3c287b0152c7/problem/CF923B?lang=zh 题意：每天都会新堆一堆雪有V[i]升，同时所有现有的雪堆都会融化T[i]升，每天总共融化了多少升雪？ 思路：用小根堆维护所有雪堆的"消失时间"，维护一个累加变量s表示已经融化的总量对于第i天的雪堆 V[i]，它能存活的天数取决于>=s。

#include<bits/stdc++.h>
using namespace std;
long long v[100010],t[100010];
priority_queue<long long, vector<long long>, greater<long long>>a;
int main(){
	long long n,s=0,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>v[i];
	for(int i=1;i<=n;i++)cin>>t[i];
	for(int i=1;i<=n;i++){
		ans=0;
		s+=t[i];
		a.push(s-t[i]+v[i]);
		while(!a.empty()&&a.top()<=s){
			ans+=a.top()-s+t[i];
			a.pop();
		}
		ans+=t[i]*a.size();
		cout<<ans<<" ";
	}
	return 0;
}

D.Rorororobot https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a548de1efbe3c287b0152c7/problem/CF1709D?lang=zh 题意：能否通过若干条指令（每条移动 k 格），从起点恰好停在终点？ 思路：列差和行差都必须是 k 的倍数，机器人可以到达的最高行是x1+(n-x1)/k*k与y1到y2间最高的封锁线对比（用st表维护）

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int f[200010][50];
int main(){
	int n,m,q;
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>a[i];
	for(int i=1;i<=m;i++)f[i][0]=a[i];
	for(int j=1;(1<<j)<=m;j++){
		for(int i=1;i+(1<<j)-1<=m;i++)f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}
	cin>>q;
	while(q--){
		int x1,y1,x2,y2,k;
		cin>>x1>>y1>>x2>>y2>>k;
		if(abs(x1-x2)%k!=0||abs(y1-y2)%k!=0){
			cout<<"NO\n";
			continue;
		}
		int p=log2(max(y1,y2)-min(y1,y2)+1);
		int b=max(f[min(y1,y2)][p],f[max(y1,y2)-(1<<p)+1][p]);
		int zx=x1+((n-x1)/k)*k;
		if(zx<=b)cout<<"NO\n";
		else cout<<"YES\n";
	}
	return 0;
}

E.Integers Have Friends https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a548de1efbe3c287b0152c7/problem/CF1548B?lang=zh 题意：给定一个由不同正整数组成的数组a。定义一个子数组为"朋友团"，当且仅当存在一个整数m>=2使得子数组中所有元素对m取模的结果都相等。求最大的朋友团的大小（即最长连续子数组的长度）。 思路：双指针用双指针维护一个滑动窗口[l,r]，使得窗口内所有相邻差值的GCD>1。每次右指针r向右扩展，如果窗口的GCD变为 1，则移动左指针l直到GCD>1。 错因：没思路，剩下时间来不及了，只够检查一下前面的题了；

#include<bits/stdc++.h>
using namespace std;
long long a[200005],b[200005],g[200005],p[200005];
long long gcd(long long x,long long y){
	while(y){
		long long r=x%y;
		x=y;
		y=r;
	}
	return x;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		if(n==1){
			cout<<1<<"\n";
			continue;
		}
		for(int i=1;i<n;i++){
			if(a[i+1]>a[i])b[i]=a[i+1]-a[i];
			else b[i]=a[i]-a[i+1];
		}
		int ans=1,sz=0;
		for(int i=1;i<n;i++){
			long long tg[200],tp[200];
			int ts=0;
			tg[++ts]=b[i];
			tp[ts]=i;
			for(int j=1;j<=sz;j++){
				long long x=gcd(g[j],b[i]);
				int u=1;
				for(int k=1;k<=ts;k++){
					if(tg[k]==x){
						if(p[j]<tp[k])tp[k]=p[j];
						u=0;
						break;
					}
				}
				if(u){
					tg[++ts]=x;
					tp[ts]=p[j];
				}
			}
			for(int j=1;j<=ts;j++){
				g[j]=tg[j];
				p[j]=tp[j];
				if(g[j]>1){
					int len=i-p[j]+2;
					if(len>ans)ans=len;
				}
			}
			sz=ts;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

F.The Treasure of The Segments https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a548de1efbe3c287b0152c7/problem/CF1462F 题意：给定n个区间[l[i],r[i]]，要删去最少的区间，使得剩下的区间构成一个"好集合"。 思路：将所有区间的左端点 l[i] 存入数组 L 并排序，将所有区间的右端点 r[i] 存入数组 R 并排序枚举每个区间 i 作为中心：left = 满足 R < l[i] 的个数（右端点小于起始位置），right = 满足 L > r[i] 的个数（左端点大于结束位置）ans = min(ans, left + right) 错因：翻译有问题，没看懂题

#include<bits/stdc++.h>
using namespace std;
int l[200005],r[200005],ll[200005],rr[200005];
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>l[i]>>r[i];
			ll[i]=l[i];
			rr[i]=r[i];
		}
		sort(ll+1,ll+n+1);
		sort(rr+1,rr+n+1);
		int ans=n;
		for(int i=1;i<=n;i++){
			int s=1,e=n,zuo=0,you=n+1;
			while(s<=e){
				int m=(s+e)/2;
				if(rr[m]<l[i]){
					zuo=m;
					s=m+1;
				}else e=m-1;
			}
			s=1,e=n;
			while(s<=e){
				int m=(s+e)/2;
				if(ll[m]>r[i]){
					you=m;
					e=m-1;
				}else s=m+1;
			}
			ans=min(ans,zuo+n-you+1);
		}
		cout<<ans<<"\n";
	}
	return 0;
}