ZROI3

문제 풀이 ZROI 3
T1
'미끄럼 창' 과 유사 하 게 단조 로 운 대기 열 로 유지 합 니 다.
#include 
#include 
#include 
#include 
#include 
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  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=m) printf("%d
",line.front().val); } return 0; } inline int read(){ char tmp=getchar(); int sum=0; bool flag=false; while(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 
#include 
#include 
#include 
#include 
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
",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'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
시험장 에서 GSS 4 와 매우 비슷 하 다 는 것 을 깨 달 았 으 나 수학 적 증명 에 패 했다.
결론: 임의의 숫자 \ (x \) 한 번 의 효과 적 인 모델 링 을 거 친 후 (모드 가 x 보다 작 음) 그 크기 는 반드시 \ (\ frac {x} {2} \ 보다 작 을 것 이다.
증명: \ (mod \ \ geq \ \ frac {x} {2} \) 이면 \ (x - mod \ \ leq \ \ frac {x} {2} \), \ (mod < \ frac {x} {2} \) 이면 \ (x)
이렇게 하면 임의의 노드 의 조작 횟수 가 \ (log 2 10 ^ 9 = 30 \) 보다 크 지 않 고 시간 복잡 도 를 보장 할 수 있 습 니 다. 나머지 세부 사항 은 GSS 4 와 대동소이 합 니 다.
#include 
#include 
#include 
#include 
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
",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'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; }

좋은 웹페이지 즐겨찾기