Lvat_s Blog

我对这次比赛无力吐槽。

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;
}