当前位置：首页 > ds >正文

李超线段树模板

ds 2025/7/19 6:30:37

P4097 【模板】李超线段树 / [HEOI2013] Segment

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>#define int long long
#define double long double
#define ull unsigned long long
#define fi first 
#define se second
#define ls(p) p<<1
#define rs(p) (p<<1)|1
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define sp(x) fixed << setprecision(x)
#define all(v) v.begin(),v.end()using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull rnd() { return (unsigned long long)rng(); }const int inf = 0x3f3f3f3f3f3f3f;
const int N = 2e6 + 5;
const int mod1 = 39989;
const int mod2 = 1e9;
const double eps = 1e-9;int n;struct node{double x;int y;
};//x表示值，y表示编号struct line{double k , b;
}p[N];//存储线段int tr[N];
int cnt = 0;//线段个数double cal(int id,int d){return p[id].b + p[id].k * d;
}int cmp(double x,double y){if(x - y > eps)return 1;if(y - x > eps)return -1;return 0;
}void add(int x,int y,int xx,int yy){cnt ++ ;if(x == xx){p[cnt].k = (double)0LL;p[cnt].b = (double)max(y , yy);}else{p[cnt].k = 1.0 * (yy - y) / (xx - x);p[cnt].b = y - p[cnt].k * x;}return;
}/*
如果新线段 f 更优，则将 f 和 g 交换。那么现在考虑在中点处 f 不如 g 优的情况：
若在左端点处 f 更优，那么 f 和 g 必然在左半区间中产生了交点，递归到左儿子中进行插入；
若在右端点处 f 更优，那么 f 和 g 必然在右半区间中产生了交点，递归到右儿子中进行插入。
若在左右端点处 g 都更优，那么 f 不可能成为答案，不需要继续下传
*/
void upd(int p,int l,int r,int u){int &v = tr[p];int mid = l+r>>1;int bmid = cmp(cal(u,mid) , cal(v , mid));//f(u) > f(v) 返回1if(bmid == 1 || ((bmid == 0) && u < v))swap(u , v);//如果新加进来的点值比原来更大 或者 一样但是编号更小 那就更新int bl = cmp(cal(u , l) , cal(v , l));int br = cmp(cal(u , r) , cal(v , r));if(bl == 1 || ((bl == 0) && u < v))upd(ls(p) , l , mid , u);if(br == 1 || ((br == 0) && u < v))upd(rs(p) , mid + 1 , r , u);return;
}void update(int p,int l,int r,int nl,int nr,int idx){if(nl <= l && r <= nr){upd(p , l , r , idx);return;}int mid = l+r>>1;if(nl <= mid)update(ls(p),l,mid,nl,nr,idx);if(nr > mid)update(rs(p),mid+1,r,nl,nr,idx);return;
}node pmax(node a,node b){if(cmp(a.x , b.x) == -1)return b;else if(cmp(a.x , b.x) == 1)return a;else{if(a.y < b.y)return a;else return b;}
}node query(int p,int l,int r,int x){if(x > r || x < l)return {0 , 0};int mid = l+r>>1;double res = cal(tr[p] , x);if(l == r){return {res , tr[p]};}return pmax({res , tr[p]} , pmax(query(ls(p) , l , mid , x) , query(rs(p) , mid + 1 , r , x)));}void solve(){cin>>n;int lastans = 0;while(n--){int op;cin>>op;if(op == 1){int x,y,xx,yy;cin>>x>>y>>xx>>yy;x = (x + lastans - 1 + mod1) % mod1 + 1;xx = (xx + lastans - 1 + mod1) % mod1 + 1;y = (y + lastans - 1 + mod2) % mod2 + 1;yy = (yy + lastans - 1 + mod2) % mod2 + 1;if(x > xx){swap(x , xx);swap(y , yy);}add(x , y , xx , yy);//把坐标转换成线段update(1 , 1 , mod1 , x , xx , cnt);//更新[x , xx]区间最大值}else{int x;cin>>x;//询问x = k时候最大y坐标为多少x = (x + lastans - 1 + mod1) % mod1 + 1;lastans = query(1 , 1 , mod1 , x).y;cout<<lastans<<"\n";}}return;
}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);time_t Start = clock();int T = 1;//cin >> T;while (T -- ){solve();}time_t End = clock(); time_t Run_time = End - Start;//cout<<"\n"<<Run_time<<"ms"<<"\n"; return 0;
}

template<class T>
struct lichaoTree{int n;int root=1;vector<int> id;vector<pair<T,T> > line;vector<int> arr;double eps=1e-6;int cntid=0;T _default=1e18;lichaoTree(){}lichaoTree(int n){init(n);}lichaoTree(int n,vector<pair<T,T> > &vec){init(n,vec);}void init(int n){this->n=n;id.assign(n<<2,{});line.clear();line.emplace_back(0,_default);cntid=0;}void init(int n,vector<pair<T,T> > &vec){this->n=n;id.assign(n<<2,{});line=vec;cntid=line.size()-1;}void print(){cout<<"LINE:\n";for(int i=1;i<=cntid;i++){cout<<line[i].first<<' '<<line[i].second<<"\n";}}T calc(int idx,int x){return line[idx].first*arr[x]+line[idx].second;}int cmpT(T a,T b){if(a-b>eps){return 1;}else if(a-b<-eps){return -1;}else{return 0;}}bool cmp(int u,int v,int x){T calu=calc(u,x),calv=calc(v,x);if(cmpT(calu,calv)==1||cmpT(calu,calv)==0&&u<v){return 1;}else{return 0;}}pair<T,int> pairmax(pair<T,int> a,pair<T,int> b){if(cmpT(a.first,b.first)==1||(cmpT(a.first,b.first)==0&&a.second<b.second)) return a;else return b;}void upd(int rt,int l,int r,int u){int &v = id[rt];int mid=(l+r)>>1;if(cmp(u,v,mid)) swap(u,v);if(cmp(u,v,l)) upd(rt<<1,l,mid,u);if(cmp(u,v,r)) upd(rt<<1|1,mid+1,r,u);}void update(int rt,int x,int y,int l,int r,int u){if(x<=l&&r<=y){upd(rt,l,r,u);return;}int mid=(l+r)>>1;if(x<=mid) update(rt<<1,x,y,l,mid,u);if(mid<y) update(rt<<1|1,x,y,mid+1,r,u);}void update(int x,int y,int u){update(root,x,y,1,n,u);}void add(int xa,int ya,int xb,int yb){if(xa==xb){line.emplace_back(0,max(ya,yb));}else{T k,b;k=1.0*(yb-ya)/(xb-xa);b=yb-xb*k;line.emplace_back(k,b);}cntid+=1;update(xa,xb,cntid);}void add(T k,T b){// usually x = [1,n]line.emplace_back(k,b);cntid+=1;update(1,n,cntid);}//y=3-2x pair<T,int > query(int rt,int l,int r,int x){if(l==r){return {calc(id[rt],x),id[rt]};}int mid=(l+r)>>1;pair<T,int> res = {calc(id[rt],x),id[rt]};if(x<=mid) res=pairmax(res,query(rt<<1,l,mid,x));if(mid<x) res=pairmax(res,query(rt<<1|1,mid+1,r,x));return res;}T queryid (int x){return query(root,1,n,x).second;}T querynum(int x){return query(root,1,n,x).first;}
};

查看全文

http://www.xdnf.cn/news/15798.html