题解 P4097 【[HEOI2013]Segment 】

2019-10-02 19:00:53


写一篇比较易于理解的题解

线段树的每个节点维护该线段的最优编号

用标记永久化

先锁定线段的位置

在将不优线段下放

(只是代表当前不优(即没有站到区间的1/2))

其实本题的细节很多。。。

但是数据很水。。。。

并且以前有大佬的复杂度有问题都可以AC。。

double=(int/int) ...

这个double和int没有区别

(一定要乘上一个1.0!!!(调试1小时。。))

最后放代码和数据生成器。。。

随手写的。。。。

//AC code
#include<bits/stdc++.h>

using namespace std;

#define mid ((l+r)>>1)
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r

inline int read(){
    int x=0,f=1;
    char p=getchar();
    while(!isdigit(p)){
        if(p=='-') f=-1;
        p=getchar();
    }
    while(isdigit(p)) x=(x<<3)+(x<<1)+p-48,p=getchar();
    return x*f;
}

const int maxn=1e6+5;
const int mod1=39989,mod2=1e9;
int n,lastans,cnt;

struct node{
    int id;
}tree[maxn<<2];

struct node1{
    double k,b;
}line[maxn];

inline void swap(int &x,int &y){
    int t=x;x=y;y=t;
}

inline void insert(int k,int l,int r,int id){
    if(l==r){
        double xid=line[id].k*l+line[id].b;
        double yid=line[tree[k].id].k*l+line[tree[k].id].b;
        if(xid>yid) tree[k].id=id;
        return;
    }
    double xmid=line[id].k*mid+line[id].b;
    double ymid=line[tree[k].id].k*mid+line[tree[k].id].b;
    double xxl=line[id].k*l+line[id].b;
    double yyl=line[tree[k].id].k*l+line[tree[k].id].b;
    double xxr=line[id].k*r+line[id].b;
    double yyr=line[tree[k].id].k*r+line[tree[k].id].b;
    if(xxl>=yyl&&xxr>=yyr){
        if(xxl!=yyl&&xxr!=yyr){
            tree[k].id=id;
            return;
        }
        if(xxl==yyl&&xxr==yyr) return;
        if(xxl==yyl){
            insert(lson,tree[k].id);
            tree[k].id=id;
            return;
        }
        if(xxr==yyr){
            insert(rson,tree[k].id);
            tree[k].id=id;
            return;
        }
    }
    if(xxl<yyl&&xxr<yyr) return ;
    if(xmid>ymid){
        int yid=tree[k].id;
        tree[k].id=id;
        if(xxl>yyl){
            insert(rson,yid);
            return;
        }
        if(xxr>yyr){
            insert(lson,yid);
            return;
        }
    }
    if(xmid<=ymid){
        if(xxl>yyl){
            insert(lson,id);
            return;
        }
        if(xxr>yyr){
            insert(rson,id);
            return;
        }
    }
}

inline void update(int k,int l,int r,int L,int R,int id){
    if(L<=l&&r<=R){
        insert(k,l,r,id);
//      cout<<"debug            "<<k<<"    "<<l<<"   "<<r<<endl;
        return;
    }
    if(L<=mid) update(lson,L,R,id);
    if(R>mid) update(rson,L,R,id);
    return ;
}

inline int query(int k,int l,int r,int pos){
    if(l==r) return tree[k].id;
    double jisk=line[tree[k].id].k*pos+line[tree[k].id].b;
    double jisx;
    if(pos<=mid){
        int x=query(lson,pos);
        jisx=line[x].k*pos+line[x].b;
        if(jisk==jisx) return min(x,tree[k].id);
        if(jisk>jisx) return tree[k].id;
        if(jisk<jisx) return x;
    }
    else{
        int x=query(rson,pos);
        jisx=line[x].k*pos+line[x].b;
        if(jisk==jisx) return min(x,tree[k].id);
        if(jisk>jisx) return tree[k].id;
        if(jisk<jisx) return x;     
    }
}

int main(){
//  freopen("data.in","r",stdin);
//  freopen("man.txt","w",stdout);
    n=read();
    while(n--){
        int opt=read();
        if(opt==1){
            int xx0=read(),yy0=read(),xx1=read(),yy1=read();
            xx0=(xx0+lastans-1)%mod1+1,yy0=(yy0+lastans-1)%mod2+1;
            xx1=(xx1+lastans-1)%mod1+1,yy1=(yy1+lastans-1)%mod2+1;
            if(xx0>xx1) swap(xx0,xx1),swap(yy0,yy1);
            if(xx0==xx1){
                line[++cnt].k=0;
                line[cnt].b=max(yy1,yy0);
            }
            else{
                line[++cnt].k=(1.0*(yy0-yy1))/(1.0*(xx0-xx1));
                line[cnt].b=yy0-xx0*line[cnt].k;
            }
//          cout<<xx0<<" "<<yy0<<" "<<xx1<<" "<<yy1<<" "<<line[cnt].k<<"   "<<line[cnt].b<<endl;            
            update(1,1,mod1,xx0,xx1,cnt);
            continue;
        }
        if(opt==0){
            int x=read();
            x=(x+lastans-1)%mod1+1;
            printf("%d\n",lastans=query(1,1,mod1,x));
            continue;
        }
    }
    return 0;
}

方便大家写锅对拍。。。。

// maker
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include<ctime>
#include <vector>
#include <set>
#define ll long long
const int N=100010;
using namespace std;
inline int rnd() {
    int res=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)) {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)) {
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res*f;
}
inline void wr(int x) {
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(x>9) wr(x/10);
    putchar(x%10+'0');
}
int n,m,Q,mx,x;
int tong[N];
inline int R(int x) {
    return (rand())%x+1;
}
int main() {
    freopen("data.in","w",stdout);
    srand((long long)time(0));
    n=100000;
    cout<<n<<endl;
    for(int i=1; i<=n; i++) {
        x=R(2)-1;
        if(x==1){
            cout<<1<<" ";
            int xx1=R(39989);
            int yy1=R(1000000000);
            int xx2=R(39989);
            int yy2=R(1000000000);
            cout<<xx1<<" "<<yy1<<" "<<xx2<<" "<<yy2<<endl;
        }
        if(x==0){
            cout<<0<<" ";
            int x=R(39989);
            cout<<x<<endl;
        }
    }
    return 0;
}