萌新求助

用李超线段树做的

题目 [HEOI2013]Segment

样例没过

谢啦！！

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
    T x = 0,f = 1;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
    while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
    return x * f;
}
const int MAXN = 4e4,mod = 39989,mod2 = 1e9,N = 39989;
namespace lichao_tree
{
    int cnt = 0;
    struct node
    {
        double k,b;
        int flag,l,r;
        node mk(double _k,double _b,int _l,int _r)
        {
            node p;p.k = _k,p.b = _b,p.flag = ++cnt,l = _l,r = _r;
            return p;
        }
        double gety(int x)
        {
            return k * x + b;
        }
    }tree[MAXN << 2],T;
    inline node query(int k,int l,int r,int x)
    {
        if(l == r) return tree[k];
        int mid = l + r >> 1;
        node g;
        if(x <= mid) 
        {
            g = query(k << 1,l,mid,x);
            printf("{%d,%d,%d}\n",l,mid,g.flag);
        }
        else {
            g = query(k << 1 | 1,mid + 1,r,x);
            printf("{%d,%d,%d}\n",mid + 1,r,g.flag);
        }
        if(g.gety(x) > tree[k].gety(x)) return g;
        return tree[k];
    }
    inline void build(int k,int l,int r)
    {
        tree[k].l = tree[k].r = 0;
        tree[k].b = tree[k].k = tree[k].flag = 0;
        if(l == r) return;
        int mid = l + r >> 1;
        build(k << 1,l,mid);
        build(k << 1 | 1,mid + 1,r);
    }
    inline void insert(int k,int l,int r,node p)
    {
        if(p.l <= l&&r <= p.r)
        {
            if(!tree[k].flag||(p.gety(l) >= tree[k].gety(l)&&p.gety(r) >= tree[k].gety(r)))
            {
                tree[k] = p;
                return;
            }
            if(l == r||(p.gety(l) <= tree[k].gety(l)&&p.gety(r) <= tree[k].gety(r))) return;
            int mid = l + r >> 1;
            if(p.gety(mid) > tree[k].gety(mid)) swap(p,tree[k]);
            if(p.gety(l) >= tree[k].gety(l)) insert(k << 1,l,mid,p);
            if(p.gety(r) >= tree[k].gety(r)) insert(k << 1 | 1,mid + 1,r,p);
            return;
        }
        int mid = l + r >> 1;
        if(p.l <= mid) insert(k << 1,l,mid,p);
        if(mid < p.r) insert(k << 1 | 1,mid + 1,r,p);
    }
}
using namespace lichao_tree;
int main()
{
    int n = Read(1),last_ = 0;
    build(1,1,N);
    while(n--)
    {
        int c = Read(1);
        if(c & 1)
        {
            int x[2],y[2];
            for(reg i = 0;i < 2;i++) x[i] = (Read(1) + last_ - 1) % mod + 1,y[i] = (Read(1) + last_ - 1) % mod2 + 1;
            if(x[0] == x[1]) continue;
            if(x[0] > x[1]) swap(x[0],x[1]),swap(y[0],y[1]);
            double k = 1.0 * (y[1] - y[0]) / (x[1] - x[0]);
            insert(1,1,N,T.mk(k,y[1] - 1.0 * x[1] * k,x[0],x[1]));
//          printf("[%f,%f]\n",x[0],x[1]);
        } else {
            int x = (Read(1) + last_ - 1) % mod + 1;
//          printf("[%d]\n",x);
            last_ = query(1,1,N,x).flag;
            printf("%d\n",last_);
        }
    }
    return 0;
}