作业

P1890 gcd区间

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e3+5,M=2e6+5;
int n,m,lg[N],f[N][15],a[N];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)f[i][0]=a[i];
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int j=1;j<=12;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			f[i][j]=__gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	while(m--){
		int l,r;
		cin>>l>>r;
		int len=r-l+1;
		int j=lg[len],ans;
		ans=__gcd(f[l][j],f[r-(1<<j)+1][j]);
		cout<<ans<<endl;
	}
	return 0;
}

P1714 切蛋糕

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5,M=2e6+5;
int n,m,lg[N],f[N][25],a[N],ma=-1e18,s[N];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)f[i][0]=a[i]+f[i-1][0];
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int j=1;j<=21;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
			//ma=max(ma,f[i][j]);
		}
	}
	int j=lg[m],ans=0;
	for(int i=m;i<=n;i++){
		ans=max(ans,f[i][0]-min(f[i-m][j],f[i-(1<<j)+1][j]));
	}cout<<ans;
	return 0;
}

重写

P2698 [USACO12MAR] Flowerpot S

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5,M=2e6+5;
int n,m,lg[N],f[N][30],D,ans=1e18,g[N][30];
struct node{
	int x,y;
}a[N];
bool cmp(node a,node b){
	return a.x<b.x;
}
bool check(int l,int r){
	int j=lg[r-l+1],ma=max(f[l][j],f[r-(1<<j)+1][j]),mi=min(g[l][j],g[r-(1<<j)+1][j]);
	if(ma-mi>=D)return 1;
	return 0;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>D;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)f[i][0]=a[i].y,g[i][0]=a[i].y;
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
			g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		int l=i-1,r=n+1,mid;
		while(l+1<r){
			mid=l+r>>1;
			if(check(i,mid)){
				r=mid;
				
			}
			else l=mid;
		}
		if(r<=n)ans=min(ans,a[r].x-a[i].x);
	}
	if(ans==1e18)cout<<-1;
	else cout<<ans;
	return 0;
}

P2866 [USACO06NOV] Bad Hair Day S

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5,M=2e6+5;
int n,lg[1000005],f[N][25],a[N];
int sum;
bool check(int l,int r){
	int j=lg[r-l+1];
	int ans=max(f[l][j],f[r-(1<<j)+1][j]);
	if(a[l-1]>ans)return 1;
	return 0;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)f[i][0]=a[i];
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		int mid,l=i,r=n+1;
		while(l+1<r){
			mid=(l+r)>>1;
			if(check(i+1,mid)){
				l=mid;
			}
			else r=mid;
		}
		sum+=l-i;
	}cout<<sum;
	return 0;
}