题解 ZROI3

T1

与《滑动窗口》类似，用单调队列维护

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define lor(a,b,c) for(register int a=b;a<=c;++a)

#define ror(a,b,c) for(register int a=c;a>=b;--a)

#define tor(a,b) for(register int a=head[b];a;a=nxt[a])

const int MAX=1e5+5;

int n,m,input,num[MAX];

struct data{

	int val,pos;

};

deque <data> line;

inline int read();

int main(){

	#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

	// freopen("test.out","w",stdout);

	#endif

	m=read();

	while(input=read(),input!=-1){

		num[++n]=input;

	}

	lor(i,1,n){

		while(!line.empty()&&line.front().pos<i-m+1) line.pop_front();

		while(!line.empty()&&line.back().val<=num[i]) line.pop_back();

		line.push_back((data){num[i],i});

		if(i>=m) printf("%d\n",line.front().val);

	}

	return 0;

}

inline int read(){

	char tmp=getchar(); int sum=0; bool flag=false;

	while(tmp<'0'||tmp>'9'){

		if(tmp=='-') flag=true;

		tmp=getchar();

	}

	while(tmp>='0'&&tmp<='9'){

		sum=(sum<<1)+(sum<<3)+tmp-'0';

		tmp=getchar();

	}

	return flag?-sum:sum;

}

T2

看起来是树链剖分..但其实用不着。由于只有”子树“相关的操作，因此把树打成DFS序后修改连续的区间即可

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define lor(a,b,c) for(register int a=b;a<=c;++a)

#define ror(a,b,c) for(register int a=c;a>=b;--a)

#define tor(a,b) for(register int a=head[b];a;a=nxt[a])

const int MAX=1e5+5;

int n,m; char input[MAX];

int root=1,ecnt,edge[MAX<<1],head[MAX],nxt[MAX<<1];

int hei[MAX],size[MAX],fa[MAX],ind[MAX],rev[MAX];

int val[MAX<<2],sum[MAX<<2],lazy_rev[MAX<<2];

inline int read();

inline void insert(int,int,int);

void dfs(int,int);

void build(int,int,int);

int print(int,int,int,int);

void change(int,int,int,bool);

void pushdown(int,int,int);

void modify_rev(int,int,int,int,int);

int query(int,int,int,int,int);

int main(){

	#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

	#endif

	n=read(); m=read(); cin>>input+1;

	lor(i,1,n-1){

		int u=read(),v=read();

		insert(u,v,++ecnt); insert(v,u,++ecnt);

	}

	dfs(root,root);

	build(1,1,n);

	lor(i,1,m){

		char type; int x; cin>>type; x=read();

		switch(type){

			case 'S':

			modify_rev(1,1,n,rev[x],rev[x]+size[x]-1);

			break;

			case 'Q':

			printf("%d\n",query(1,1,n,rev[x],rev[x]+size[x]-1));

			break;

		}

	}

	return 0;

}

inline int read(){

	char tmp=getchar(); int sum=0; bool flag=false;

	while(tmp<'0'||tmp>'9'){

		if(tmp=='-') flag=true;

		tmp=getchar();

	}

	while(tmp>='0'&&tmp<='9'){

		sum=(sum<<1)+(sum<<3)+tmp-'0';

		tmp=getchar();

	}

	return flag?-sum:sum;

}

inline void insert(int from,int to,int id){

	nxt[id]=head[from]; head[from]=id; edge[id]=to;

}

void dfs(int u,int f){

	hei[u]=hei[f]+1;

	fa[u]=f;

	ind[++ind[0]]=u;

	rev[u]=ind[0];

	tor(i,u){

		int v=edge[i]; if(v==f) continue;

		dfs(v,u);

		size[u]+=size[v];

	}

	size[u]++;

}

void build(int p,int l,int r){

	if(l==r) {val[p]=input[ind[l]]-'0'; sum[p]=val[p]==1; return;}

	int mid=(l+r)>>1;

	build(p<<1,l,mid); build(p<<1|1,mid+1,r);

	sum[p]=sum[p<<1]+sum[p<<1|1];

}

int print(int p,int l,int r,int k){

	if(l==k&&k==r) return val[p];

	pushdown(p,l,r);

	int mid=(l+r)>>1;

	if(k<=mid) return print(p<<1,l,mid,k);

	if(mid+1<=k) return print(p<<1|1,mid+1,r,k);

}

void change(int p,int l,int r,bool rev){

	lazy_rev[p]^=rev;

	if(rev) sum[p]=(r-l+1)-sum[p];

	if(l==r){

		if(lazy_rev[p]) val[p]^=1;

		lazy_rev[p]=false;

	}

}

void pushdown(int p,int l,int r){

	if(!lazy_rev[p]) return;

	int mid=(l+r)>>1;

	change(p<<1,l,mid,lazy_rev[p]);

	change(p<<1|1,mid+1,r,lazy_rev[p]);

	lazy_rev[p]=false;

}

void modify_rev(int p,int l,int r,int L,int R){

	if(L<=l&&r<=R) {change(p,l,r,true); return;}

	pushdown(p,l,r);

	int mid=(l+r)>>1;

	if(L<=mid) modify_rev(p<<1,l,mid,L,R);

	if(mid+1<=R) modify_rev(p<<1|1,mid+1,r,L,R);

	sum[p]=sum[p<<1]+sum[p<<1|1];

}

int query(int p,int l,int r,int L,int R){

	if(L<=l&&r<=R) return sum[p];

	pushdown(p,l,r);

	int mid=(l+r)>>1,ans=0;

	if(L<=mid) ans+=query(p<<1,l,mid,L,R);

	if(mid+1<=R) ans+=query(p<<1|1,mid+1,r,L,R);

	return ans;

}

T3

在考场上就意识到了和GSS4极其相似，但败在了数学证明上..

结论:任意数字\(x\)经过一次有效的取模之后（模数小于 x），其大小必定小于\(\frac{x}{2}\)

证明：若 \(mod\geq \frac{x}{2}\),则\(x-mod\leq \frac {x}{2}\)；若\(mod < \frac{x}{2}\),则\(x <mod \leq \frac{x}{2}\)

这样就可以保证任意节点的操作次数不大于\(log_2 10^9=30\)，时间复杂度得到保证。其余细节与GSS4大同小异

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

#define lor(a,b,c) for(register int a=b;a<=c;++a)

const int MAX=1e5+5;

int n,m; ll init[MAX];

ll val_max[MAX<<2],val_sum[MAX<<2];

inline int read();

void build(int,int,int);

void modify_mod(int,int,int,int,int,ll);

void modify_as(int,int,int,int,ll);

ll query(int,int,int,int,int);

int main(){

	#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

	#endif

	n=read(); m=read();

	lor(i,1,n) scanf("%lld",&init[i]);

	build(1,1,n);

	lor(i,1,m){

		int type,l,r; ll x; type=read();

		switch(type){

			case 1:

			l=read(); r=read();

			printf("%lld\n",query(1,1,n,l,r));

			break;

			case 2:

			l=read(); r=read(); scanf("%lld",&x);

			modify_mod(1,1,n,l,r,x);

			break;

			case 3:

			l=read(); scanf("%lld",&x);

			modify_as(1,1,n,l,x);

			break;

		}

	}

	return 0;

}

inline int read(){

	char tmp=getchar(); int sum=0; bool flag=false;

	while(tmp<'0'||tmp>'9'){

		if(tmp=='-') flag=true;

		tmp=getchar();

	}

	while(tmp>='0'&&tmp<='9'){

		sum=(sum<<1)+(sum<<3)+tmp-'0';

		tmp=getchar();

	}

	return flag?-sum:sum;

}

void build(int p,int l,int r){

	if(l==r) {val_sum[p]=val_max[p]=init[l]; return;}

	int mid=(l+r)>>1;

	build(p<<1,l,mid); build(p<<1|1,mid+1,r);

	val_sum[p]=val_sum[p<<1]+val_sum[p<<1|1];

	val_max[p]=max(val_max[p<<1],val_max[p<<1|1]);

}

void modify_mod(int p,int l,int r,int L,int R,ll k){

	if(l==r) {val_sum[p]%=k; val_max[p]=val_sum[p]; return;}

	int mid=(l+r)>>1;

	if(L<=mid&&val_max[p<<1]>=k) modify_mod(p<<1,l,mid,L,R,k);

	if(mid+1<=R&&val_max[p<<1|1]>=k) modify_mod(p<<1|1,mid+1,r,L,R,k);

	val_sum[p]=val_sum[p<<1]+val_sum[p<<1|1];

	val_max[p]=max(val_max[p<<1],val_max[p<<1|1]);

}

void modify_as(int p,int l,int r,int pos,ll k){

	if(l==pos&&pos==r) {val_sum[p]=k; val_max[p]=k; return;}

	int mid=(l+r)>>1;

	if(pos<=mid) modify_as(p<<1,l,mid,pos,k);

	if(mid+1<=pos) modify_as(p<<1|1,mid+1,r,pos,k);

	val_sum[p]=val_sum[p<<1]+val_sum[p<<1|1];

	val_max[p]=max(val_max[p<<1],val_max[p<<1|1]);

}

ll query(int p,int l,int r,int L,int R){

	if(L<=l&&r<=R) return val_sum[p];

	int mid=(l+r)>>1; ll ans=0;

	if(L<=mid) ans+=query(p<<1,l,mid,L,R);

	if(mid+1<=R) ans+=query(p<<1|1,mid+1,r,L,R);

	return ans;

}

巴特西

ZROI3

题解 ZROI3

T1

T2

T3

最新文章

热门文章