2015.01.04集训总结

Task#1 Contest

面对三道傻逼题本沙茶妥妥爆零.大家一起喊出来我弱不弱,弱不弱?

T1题目大意:傻逼题,大家通过代码来猜测什么题目吧.(多带了一个\(log\)结果没有超时,反而由于空间问题被卡了2MB内存,艹!)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 100010
struct Node{
	int l,r,siz;
}S[N*20];int cnt;
int Newv(int last,int tl,int tr,int ins){
	int q=++cnt;S[q]=S[last],++S[q].siz;if(tl==tr)return q;
	int mid=(tl+tr)>>1;
	if(ins<=mid)S[q].l=Newv(S[last].l,tl,mid,ins);else S[q].r=Newv(S[last].r,mid+1,tr,ins);
	return q;
}
int Query(int q,int tl,int tr,int dl,int dr){
	if(dl<=tl&&tr<=dr)return S[q].siz;
	int mid=(tl+tr)>>1;
	if(dl>mid)return Query(S[q].r,mid+1,tr,dl,dr);
	else if(dr<=mid)return Query(S[q].l,tl,mid,dl,dr);
	else return Query(S[q].l,tl,mid,dl,mid)+Query(S[q].r,mid+1,tr,mid+1,dr);
}
struct Case{
	int x,y;
	bool operator<(const Case&B)const{return x<B.x;}
}C[N];
int p[N],q[N],root[N];
int main(){
	freopen("permutation.in","r",stdin),freopen("permutation.out","w",stdout);
	int n;cin>>n;register int i,j;
	for(i=1;i<=n;++i)scanf("%d",&p[i]),C[p[i]].x=i;for(i=1;i<=n;++i)scanf("%d",&q[i]),C[q[i]].y=i;
		sort(C+1,C+n+1);
	for(i=1;i<=n;++i)root[i]=Newv(root[i-1],1,n,C[i].y);
	int lans=0,a,b,c,d,aa,bb,cc,dd,q;scanf("%d",&q);
	while(q--){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		aa=(a-1+lans)%n+1,bb=(b-1+lans)%n+1,cc=(c-1+lans)%n+1,dd=(d-1+lans)%n+1;
		a=min(aa,bb),b=max(aa,bb),c=min(cc,dd),d=max(cc,dd);
		printf("%d\n",(lans=Query(root[b],1,n,c,d)-Query(root[a-1],1,n,c,d)+1)-1);
	}return 0;
	fclose(stdin),fclose(stdout);return 0;

}

T2:见下面的链接

http://wyfcyx.is-programmer.com/posts/75155.html

T3:见下面的链接

http://wyfcyx.is-programmer.com/posts/75156.html

Task#2 后缀数组及其应用

现在没时间,等我找到特别有意思的题目来做吧~~~