暴力。。
#include<cstdio>
int n,cir[25],sum[25],ans=0;
int main(){
freopen("1800.in","r",stdin);
freopen("1800.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&cir[i]);sum[i]=cir[i]+sum[i-1];}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
for(int k=j+1;k<=n;k++){
for(int l=k+1;l<=n;l++){
if(sum[j-1]-sum[i-1]==sum[l-1]-sum[k-1] && sum[k-1]-sum[j-1]==sum[n]-sum[l-1]+sum[i-1])ans++;
}
}
}
}
printf("%d\n",ans);
return 0;
}
第一次写分块，挑了这题写……
然后调了一个晚上。
各种猎奇的错误都被我犯了……
人傻就是要多做题。
分块+二分
参考hzwer的
弱智错误记录:
1.数组要注意清空:这个在WC2016上已经让我的T1 60->0了……以后要认真吸取教训
2.不要乱开局部数组:这样会显著增大常数
3.要知道自己二分的是什么，不要搞着搞着就搞乱了
以上
Claris也在坚持刷题……太可怕了，本身实力超强还在刷……orzzzz
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int n,c,m,a[100005],f[1505][1505],fir[100005],las[100005],block,ans=0,L[1505],R[1505],belong[100005],tmp[100005],cnt;
struct Data{
int a,b;
friend bool operator<(Data a,Data b){
return (a.a<b.a)||(a.a==b.a && a.b<b.b);
}
}data[100005];
pair<int,int> GetLR(int L,int R){
L=(L+ans)%n+1;
R=(R+ans)%n+1;
if(L>R)swap(L,R);
return make_pair(L,R);
}
void Pre(){
for(int i=1;i<=cnt;i++){
for(int j=L[i];j<=n;j++)tmp[a[j]]=0;
int tot=0;
for(int j=L[i];j<=n;j++){
if(tmp[a[j]]%2==0 && tmp[a[j]])tot--;
tmp[a[j]]++;
if(tmp[a[j]]%2==0)tot++;
f[i][belong[j]]=tot;
}
}
//for(int i=belong[1];i<=belong[n];i++){for(int j=i;j<=belong[n];j++){printf("%d ",f[i][j]);}putchar('\n');}
for(int i=1;i<=n;i++)data[i].a=a[i],data[i].b=i;
sort(data+1,data+n+1);
for(int i=1;i<=n;i++){
if(fir[data[i].a]==0)fir[data[i].a]=i;
las[data[i].a]=i ;
}
}
int Ef_Fir(int x,int v){
int tp=214748364,l=fir[v],r=las[v];
while(l<=r){
int mid=l+r>>1;
if(x>data[mid].b)l=mid+1;
else {r=mid-1;tp=mid;}
}
return tp;
}
int Ef_Las(int x,int v){
int tp=0,l=fir[v],r=las[v];
while(l<=r){
int mid=l+r>>1;
if(x<data[mid].b)r=mid-1;
else {l=mid+1;tp=mid;}
}
return tp;
}
int Ef(int x,int y,int v){
//printf("%d %d %d | EF:%d %d\n",x,y,v,Ef_Las(y,v),Ef_Fir(x,v));
return max(Ef_Las(y,v)-Ef_Fir(x,v)+1,0);
}
int solve(int l,int r){
//printf("LR:%d %d\n",l,r);
int nwans=0,kl=belong[l],kr=belong[r];
if(kl+1==kr || kl==kr){
for(int i=l;i<=r;i++){
if(tmp[a[i]])continue;
int sp=Ef(l,r,a[i]);
if(sp%2==0){nwans++;}
//printf("%d %d %d\n",l,r,a[i]);
tmp[a[i]]=1;
}
for(int i=l;i<=r;i++)tmp[a[i]]=0;
return nwans;
}
else {
int fs=L[kl+1],la=R[kr-1];
nwans=f[kl+1][kr-1];
//printf("%d %d | NW_ANS1:%d\n",kl,kr,nwans);
for(int i=l;i<fs;i++){
if(tmp[a[i]])continue;
int sp=Ef(l,r,a[i]),sp2=Ef(fs,la,a[i]);
if(sp2%2==0 && sp%2 && sp2!=0){nwans--;}
if((sp2%2 || sp2==0) && sp%2==0){nwans++;}
//printf("SP:%d SP2:%d_%d_",sp,sp2,nwans);
tmp[a[i]]=1;
}
//printf("NW_ANS2:%d\n",nwans);
for(int i=la+1;i<=r;i++){
if(tmp[a[i]])continue;
int sp=Ef(l,r,a[i]),sp2=Ef(fs,la,a[i]);
if(sp2%2==0 && sp%2 && sp2!=0){nwans--;}
if((sp2%2 || sp2==0) && sp%2==0){nwans++;}
//printf("SP:%d SP2:%d_%d_",sp,sp2,nwans);
tmp[a[i]]=1;
}
for(int i=l;i<fs;i++)tmp[a[i]]=0;
for(int i=la+1;i<=r;i++)tmp[a[i]]=0;
return nwans;
}
}
void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
int main(){
freopen("2821.in","r",stdin);
freopen("2821.out","w",stdout);
Read(n);Read(c);Read(m);
for(int i=1;i<=n;i++){
Read(a[i]);
}
block=(int)sqrt((double)n/log(n)*log(2));
cnt=n/block+(n%block!=0);
for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1;
for(int i=1;i<=cnt;i++)L[i]=R[i-1]+1,R[i]=i*block;
R[cnt]=n;
Pre();
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=m;i++){
int tl,tr;
Read(tl);Read(tr);
pair<int,int> Ask=GetLR(tl,tr);
//pair<int,int> Ask=make_pair(tl,tr);
ans=solve(Ask.first,Ask.second);
printf("%d\n",ans);
}
return 0;
}
真的是完美的滚粗，不能更滚粗了……第一次去WC滚粗很正常gqy等一群大爷也第一次去就Ag了……
day 0
到了绵阳……和cjy wlp lyz三个大爷住在一起 感觉十分资瓷
晚上睡觉感觉很冷谁叫你不把衣服放被子上
day 1
早上Picks的课上完后，觉的自己幼儿园毕业都算不上
下午睡掉了
晚上隔膜
营员交流wzf和nxy讲的东西完全不会啊
day 2
早上难得听了课！但是还是睡掉了
下午继续睡觉
晚上隔膜
营员交流lzz还是很资瓷的
day3
早上不知所云
下午评测系统十分资瓷！
晚上隔膜
晚上试机似乎ak了……为接下来的爆0滚粗埋下伏笔
day4
早上做题啦！
三题都好难啊
T1写了一个多合一程序
T2写了个连样例都没过的暴力
T3直接弃疗
得分0+5+0
原来T1数组少清空1个……吐血
wyx强行110 Au
lzz wzf都进队了(rank2 rank3)都是160
nxy好像写挂了一题……默哀
wlp90
cjy100
晚上的晚会还是很欢乐的
本校几位大爷都表演去了
后来直接隔膜来抚慰我受伤的心情
day5
去了纪念馆
心情更加沉重了
day6
早上坐飞机回芜湖了……
滚粗胸牌回家
希望省选不能再这样滚粗了……
我对这次比赛无力吐槽。
AB正常
C真是无力吐槽
D是FST好题
E题莫队
但是我C交了八九次
最后C的分数就三百多
打比赛打成这样我都想骂人了
搞这种HACK/FST比赛，纯考细节的比赛有意思吗？
我并不是说不注重细节，但是这种细节型比赛我实在是(哔——)
最近在看博客+做题……突然发现我曾经以"Lvat2000"这个ID评论过很多文章。
然后我整个人都不好了。
现在才发现我当年是多么弱+傻逼……
谨以此文为被坑过的众博主表示道歉。
我现在看到了两个被我写过奇特评论的神犇：Vani Mato_No1
感觉这个名单还要扩充很多啊……555555555555555555555555
CDQ分治
递归处理左边的操作，再计算影响，然后处理右边的操作。
使用一个树状数组，利用排序x坐标的单调性，然后直接在树状数组上操作就行了。
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct Do{
int flag,x,y,id,v,pos;
friend bool operator <(const Do &a,const Do &b){
return a.x==b.x?(a.y==b.y?a.pos<b.pos:a.y<b.y):a.x<b.x;
}
}Q[200005],tmp[200005];
int s,w,tot,_Y[210005],toty,ans[10005],totans,BIT[200005],t1,t2,cnt;
int lowbit(int x){
return x&(-x);
}
void Add(int pos,int val){
while(pos<=toty){
BIT[pos]+=val;
pos+=lowbit(pos);
}
}
int Query(int pos){
int ans=0;
while(pos){
ans+=BIT[pos];
pos-=lowbit(pos);
}
return ans;
}
void CDQ(int l,int r){
if(l==r)return;
int mid=l+r>>1,t1=l,t2=mid+1;
for(int i=l;i<=r;i++){
//printf("Hello!:%d %d %d %d %d\n",Q[i].id,mid,Q[i].flag,Q[i].fg,Q[i].pos);
if(Q[i].id<=mid && Q[i].flag==1){Add(Q[i].y,Q[i].v);/*printf("Reggle:%d %d\n",Query(Q[i].y),Q[i].v);*/}
if(Q[i].id>mid && Q[i].flag==2){/*puts("233");printf("Leggle:%d\n",Query(Q[i].y));*/ans[Q[i].pos]+=Q[i].v*Query(Q[i].y);}
}
for(int i=l;i<=r;i++){
if(Q[i].id<=mid && Q[i].flag==1)Add(Q[i].y,-Q[i].v);
}
for(int i=l;i<=r;i++){
if(Q[i].id<=mid)tmp[t1++]=Q[i];
else tmp[t2++]=Q[i];
}
for(int i=l;i<=r;i++){
Q[i]=tmp[i];
}
CDQ(l,mid);
CDQ(mid+1,r);
}
int main(){
freopen("1176.in","r",stdin);
freopen("1176.out","w",stdout);
scanf("%d %d",&s,&w);
while(scanf("%d",&Q[++tot].flag)!=EOF){
if(Q[tot].flag==3){tot--;break;}
if(Q[tot].flag==1){
scanf("%d %d %d",&Q[tot].x,&Q[tot].y,&Q[tot].v);
_Y[++toty]=Q[tot].y;
Q[tot].id=tot;
Q[tot].pos=0;
}
else {
int x1,x2,y1,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
ans[++cnt]=s*(x2-x1+1)*(y2-y1+1);
Q[tot].x=x1-1;
Q[tot].y=y1-1;
Q[tot].id=tot;
Q[tot].pos=cnt;
Q[tot].v=1;
_Y[++toty]=Q[tot].y;
tot++;
Q[tot].flag=2;
Q[tot].x=x2;
Q[tot].y=y1-1;
Q[tot].id=tot;
Q[tot].pos=cnt;
Q[tot].v=-1;
tot++;
Q[tot].flag=2;
Q[tot].x=x1-1;
Q[tot].y=y2;
Q[tot].id=tot;
_Y[++toty]=Q[tot].y;
Q[tot].pos=cnt;
Q[tot].v=-1;
tot++;
Q[tot].flag=2;
Q[tot].x=x2;
Q[tot].y=y2;
Q[tot].pos=cnt;
Q[tot].id=tot;
Q[tot].v=1;
}
}
sort(_Y+1,_Y+toty+1);
toty=unique(_Y+1,_Y+toty+1)-_Y-1;
for(int i=1;i<=tot;i++){
Q[i].y=lower_bound(_Y+1,_Y+toty+1,Q[i].y)-_Y;
}
sort(Q+1,Q+tot+1);
CDQ(1,tot);
for(int i=1;i<=cnt;i++){
printf("%d\n",ans[i]);
}
return 0;
}
CLJ的题目真是猛……我调了一个晚上……才发现是开始的排序出了问题……真是……人弱没办法……
二分+可持久化线段树。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,Q,a[20005],b[20005],m,root[20005],cnt,ms[4],ans;
pair<int,int> s[20005];
struct SegTree{
int nl,nr,cnt,lx,rx;
}tree[1000005];
void OutNode(SegTree d){
puts("\nThis is a SegTree Node:");
printf("nl:%d nr:%d cnt:%d lx:%d rx:%d\n\n",d.nl,d.nr,d.cnt,d.lx,d.rx);
}
void OutTree(int l,int r,int root){
printf("%d %d The Tree:%d %d %d\n",l,r,tree[root].lx,tree[root].cnt,tree[root].rx);
if(l==r)return;
int mid=l+r>>1;
OutTree(l,mid,tree[root].nl);
OutTree(mid+1,r,tree[root].nr);
}
void Pushup(int root){
tree[root].lx=max(tree[tree[root].nl].lx,tree[tree[root].nl].cnt+tree[tree[root].nr].lx);
tree[root].rx=max(tree[tree[root].nr].rx,tree[tree[root].nr].cnt+tree[tree[root].nl].rx);
tree[root].cnt=tree[tree[root].nl].cnt+tree[tree[root].nr].cnt;
}
void Build(int l,int r,int &root){
root=++cnt;
if(l==r){
tree[root].lx=1;
tree[root].rx=1;
tree[root].cnt=1;
tree[root].nl=0;
tree[root].nr=0;
//printf("--------------------L:%d\n",l);
return;
}
int mid=l+r>>1;
Build(l,mid,tree[root].nl);
Build(mid+1,r,tree[root].nr);
Pushup(root);
return;
}
void Update(int l,int r,int &root,int lastroot,int pos){
root=++cnt;
tree[root].nl=tree[lastroot].nl;
tree[root].nr=tree[lastroot].nr;
if(l==r){
tree[root].cnt=-1;
tree[root].lx=-1;
tree[root].rx=-1;
//printf("----------------------R:%d\n",tree[root].rx);
return;
}
int mid=l+r>>1;
if(pos<=mid)Update(l,mid,tree[root].nl,tree[lastroot].nl,pos);
else Update(mid+1,r,tree[root].nr,tree[lastroot].nr,pos);
Pushup(root);
}
SegTree Ask(int root,int l,int r,int L,int R){
if(l>r)return tree[0];
if(L>=l && R<=r)return tree[root];
int mid=L+R>>1;
SegTree a=tree[0],b=tree[0];
if(l>mid)return Ask(tree[root].nr,l,r,mid+1,R);
if(r<=mid)return Ask(tree[root].nl,l,r,L,mid);
a=Ask(tree[root].nl,l,r,L,mid);
b=Ask(tree[root].nr,l,r,mid+1,R);
SegTree c;
c.lx=max(a.lx,a.cnt+b.lx);
c.rx=max(b.rx,b.cnt+a.rx);
c.cnt=a.cnt+b.cnt;
//OutNode(c);
return c;
}
int Query(){
int l=1,r=n+1,Ans=0;
while(l<r){
int mid=l+r>>1;
SegTree a=Ask(root[mid],ms[0],ms[1],1,m),b=Ask(root[mid],ms[1]+1,ms[2]-1,1,m),c=Ask(root[mid],ms[2],ms[3],1,m);
//OutTree(1,n,root[mid]);
//printf("MID:%d %d %d %d %d\n",mid,root[mid],a.rx,b.cnt,c.lx);
int sum=a.rx+b.cnt+c.lx;
if(sum>=0)l=mid+1,Ans=mid;
else r=mid;
}
return Ans;
}
int main(){
//freopen("2653.in","r",stdin);
//freopen("2653.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
m=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+m+1,a[i])-b;s[i].first=a[i];s[i].second=i;/*printf("Ai:%d\n",a[i]);*/}
sort(s+1,s+n+1);
//for(int i=1;i<=n;i++)printf("Si:%d\n",s[i].second);
Build(1,m,root[1]);
for(int i=2;i<=n;i++)Update(1,m,root[i],root[i-1],s[i-1].second);
scanf("%d",&Q);
while(Q--){
scanf("%d %d %d %d",&ms[0],&ms[1],&ms[2],&ms[3]);
ms[0]=(ms[0]+ans)%n+1;
ms[1]=(ms[1]+ans)%n+1;
ms[2]=(ms[2]+ans)%n+1;
ms[3]=(ms[3]+ans)%n+1;
sort(ms,ms+4);
//printf("MS:%d %d %d %d\n",ms[0],ms[1],ms[2],ms[3]);
ans=b[Query()];
//printf("QUERY:%d\n",Query());
printf("%d\n",ans);
}
return 0;
}
很久没更新了呢。
这题我写的是可持久化线段树版本的。
代码参考了hzwer的，orzzzzzzzzzzzz
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,m,h[100005],root[100005],en,lca[100005][20],a[100005],b[100005],deep[100005],es,dfn[100005],pos[100005],dfscnt,cnt,ans=0;
struct Edge{
long long b,next;
}e[200005];
struct SegTree{
long long nl,nr,v;
}tree[3000005];
void Add(long long sa,long long sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
long long LCA(long long u,long long v){
if(deep[u]<deep[v])swap(u,v);
long long sou=deep[u]-deep[v];
for(long long i=0;i<=18;i++)if((1<<i)&sou)u=lca[u][i];
for(long long i=18;i>=0;i--)if(lca[u][i]!=lca[v][i]){u=lca[u][i];v=lca[v][i];}
if(u==v)return u;
return lca[u][0];
}
void DFS(long long u){
dfn[++dfscnt]=u;
pos[u]=dfscnt;
for(long long i=1;i<=18;i++){
if((1<<i)<=deep[u])lca[u][i]=lca[lca[u][i-1]][i-1];
else break;
}
for(long long i=h[u];i;i=e[i].next){
long long v=e[i].b;
if(lca[u][0]!=v){
deep[v]=deep[u]+1;
lca[v][0]=u;
DFS(v);
}
}
}
long long Query(long long a,long long bs,long long c){
long long Lca=LCA(a,bs);
//printf("ABCD:%lld %lld %lld %lld\n",pos[a],pos[bs],pos[Lca],pos[lca[Lca][0]]);
long long sa=root[pos[a]],sb=root[pos[bs]],sc=root[pos[Lca]],sd=root[pos[lca[Lca][0]]];
long long l=1,r=es;
while(l<r){
long long mid=l+r>>1,Sum=tree[tree[sa].nl].v+tree[tree[sb].nl].v-tree[tree[sc].nl].v-tree[tree[sd].nl].v;
//printf("SUM:%lld\n",Sum);
if(Sum>=c){r=mid;sa=tree[sa].nl;sb=tree[sb].nl;sc=tree[sc].nl;sd=tree[sd].nl;}
else {c-=Sum;l=mid+1;sa=tree[sa].nr;sb=tree[sb].nr;sc=tree[sc].nr;sd=tree[sd].nr;}
}
return b[l];
}
void Update(long long l,long long r,long long &root,long long lastroot,long long pos){
root=++cnt;
tree[root].v=tree[lastroot].v+1;
if(l==r)return;
tree[root].nl=tree[lastroot].nl;
tree[root].nr=tree[lastroot].nr;
long long mid=l+r>>1;
if(pos<=mid)Update(l,mid,tree[root].nl,tree[lastroot].nl,pos);
else Update(mid+1,r,tree[root].nr,tree[lastroot].nr,pos);
}
int main(){
freopen("2588.in","r",stdin);
freopen("2588.out","w",stdout);
scanf("%lld %lld",&n,&m);
for(long long i=1;i<=n;i++){
scanf("%lld",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
es=unique(b+1,b+1+n)-b-1;
for(long long i=1;i<=n;i++)a[i]=lower_bound(b+1,b+es+1,a[i])-b;
for(long long i=1;i<n;i++){
long long sa,sb;
scanf("%lld %lld",&sa,&sb);
Add(sa,sb);
Add(sb,sa);
}
DFS(1);
for(long long i=1;i<=n;i++){
//printf("ROT:%lld\n",root[pos[lca[dfn[i]][0]]]);
Update(1,es,root[i],root[pos[lca[dfn[i]][0]]],a[dfn[i]]);
}
for(long long i=1;i<=m;i++){
long long a,b,c;
scanf("%lld %lld %lld",&a,&b,&c);
a^=ans;
ans=Query(a,b,c);
if(i!=m)printf("%lld\n",ans);
else printf("%lld",ans);
}
return 0;
}
退役也有一个月了。
是时候记录一下每天颓废的生活了。
11.17
知道自己爆炸了。但还是厚颜无耻的赖在竞赛机房不走。
同样悲剧的hyq syy等神犇们离开了。空荡荡的机位显得十分突兀。
11.18
强行加入计算机竞赛第二次分组。
没什么其他竞赛能搞的。只有计算机还有一线希望。
11.19
居然成功了。
但是很不光彩。
比我考的高的人走了一批。剩下的小组内的人分都比我高的多。
11.20-12.3
认真搞了一下文化课。顺便搞了OI。
12.4-12.9
ygp带着myh qns lzz去THU集训了。
我就在家里颓废。
该做的题目只做了一点点。
Thaddeus神犇已经刷到400道题了。然而我只有他的一半。在12.4后我没有A掉哪怕一道水题。
12.10
ygp回来了。
训练又要重新开始了。
想去WC玩玩，就当作是旅游了。
但是我分考太低估计不带我……那就在家颓废吧。
水平跌到了今年8月正式搞竞赛前的水准。
但是还是要为了明年的省选Bless All.(万一省选AK进队了呢？但是这是不可能的，我要能AK那么所有人都AK了)
再见，OI。或许明天我就真的被赶出机房彻底退役了。
Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com
