[Nowcoder Multi Univerisity Training 7K]Function

Link

Code

求积性函数f(n)的前缀和,其中f(1)=1,f(p^t)=1+3t[p\bmod 4=1]
有结论就简单了

Solution

const int N=1e5,XN=N+11;

int prime[XN],pcnt;
void Prep() {
    static bool notPrime[XN];
    for(int i=2;i<=N;++i) {
        if(!notPrime[i])
            prime[++pcnt]=i;
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}

std::vector<int> kp;
int n,lim,psz,id[2][XN],idc;

int ID(int x) {
    return x<=lim?id[0][x]:id[1][n/x];
}

int g[XN*2],fs[XN];
long long H(int n,int m) {
    if(n<=1 || m>psz || n<prime[m])
        return 0;
    long long res=g[ID(n)]-fs[m-1];
    for(int i=m;i<=psz && 1LL*prime[i]*prime[i]<=n;++i) {
        long long pt=prime[i];
        for(int t=1;pt<=n;++t,pt*=prime[i])
            res+=1LL*(3*t*(prime[i]%4==1)+1)*(H(n/pt,i+1)+(t!=1));
    }
    return res;
}

long long Calc(int _) {
    static int t[2][XN*2];
    kp={};idc=0;
    psz=std::upper_bound(prime+1,prime+1+pcnt,lim=sqrt(n=_)+0.5)-prime;
    for(int l=1,r;l<=n;l=r+1) {
        int x=n/l;r=n/x;
        kp.push_back(x);
        (x<=lim?id[0][x]:id[1][n/x])=++idc;
        t[0][idc]=(x/4)-1+(x%4>=1);
        t[1][idc]=(x/4)+(x%4>=3);
    }
    fs[1]=1;
    for(int i=2,psum[]={0,0};i<=psz;++i) {
        for(auto &x : kp)
            if(1LL*prime[i]*prime[i]<=x) {
                t[0^(prime[i]%4==3)][ID(x)]-=t[0][ID(x/prime[i])]-psum[0];
                t[1^(prime[i]%4==3)][ID(x)]-=t[1][ID(x/prime[i])]-psum[1];
            } else
                break;
        if(prime[i]!=2)
            psum[prime[i]%4==3]++;
        fs[i]=fs[i-1]+1+3*(prime[i]%4==1);
    }
    for(auto &x : kp)
        g[ID(x)]=4*t[0][ID(x)]+t[1][ID(x)]+(x>=2);
    return H(n,1)+1;
}

int32_t main() {
    freopen("input","r",stdin);
    Prep();
    int T;std::cin>>T;
    while(T--) {
        int n;std::cin>>n;
        std::cout<<Calc(n)<<'\n';
    }
    return 0;
}

[Nowcoder Multi Univerisity Training 4F]Merge

Link

Solution

对两个数组merge是干了一件这样的事:
将每个数组从头到尾划分成若干个部分,使得每个部分的第一个元素是一个部分中的严格最大值。那么原问题就是将所有的部分按照每个部分的第一个元素排序。
接下来显然的一点是,不会产生两个部分的合并,但是在修改操作中会产生两个部分的拆分。
用Treap即可实现,然后实际实现的时候没有必要单独存储每个块的开头然后再另外存储块中的元素。直接存原序列然后维护一下最值就可以快速得到每个元素所处块的开头位置了。
然后实际写的时候可以再抽象一点,写的时候不用考虑块的概念直接暴力模拟,然后复杂度证明再考虑块的概念。

Code

const int XN=1e5+11,INF=1e9;

struct Treap {
    struct Node {
        Node *son[2];
        int size,v,max;

        Node(int v):size(1),v(v),max(v) {
            son[0]=son[1]=null;
        }

        Node(void*):size(0),v(0),max(-INF) {
            son[0]=son[1]=this;
        }

        void Up() {
            size=son[0]->size+1+son[1]->size;
            max=std::max(v,std::max(son[0]->max,son[1]->max));
        }
    }*root;

    static Node *null;

    Treap(int a[],int n):root(Build(a,1,n)) {}

    static Node *Build(int a[],int L,int R) {
        if(L>R)
            return null;
        else {
            int M=(L+R)/2;
            Node *pos=new Node(a[M]);
            pos->son[0]=Build(a,L,M-1);
            pos->son[1]=Build(a,M+1,R);
            pos->Up();
            return pos;
        }
    }

    static std::pair<Node*,Node*> Split(Node *pos,int k) {
        if(k==0)
            return std::pair<Node*,Node*>(null,pos);
        else if(k==pos->size)
            return std::pair<Node*,Node*>(pos,null);
        else {
            std::pair<Node*,Node*> res;
            if(k<=pos->son[0]->size) {
                res=Split(pos->son[0],k);
                pos->son[0]=res.second;
                pos->Up();
                res.second=pos;
            } else {
                res=Split(pos->son[1],k-pos->son[0]->size-1);
                pos->son[1]=res.first;
                pos->Up();
                res.first=pos;
            }
            return res;
        }
    }

    static Node *Merge(Node *p1,Node *p2) {
        if(p1==null || p2==null)
            return p1==null?p2:p1;
        else {
            Node *pos;
            if(rand()%(p1->size+p2->size)+1<=p1->size) { 
                pos=p1;
                pos->son[1]=Merge(pos->son[1],p2);
                pos->Up();
            } else {
                pos=p2;
                pos->son[0]=Merge(p1,pos->son[0]);
                pos->Up();
            }
            return pos;
        }
    }

    static std::tuple<Node*,Node*,Node*> Split(Node *root,int l,int r) {
        std::pair<Node*,Node*> x=Split(root,r),y=Split(x.first,l-1);
        return std::make_tuple(y.first,y.second,x.second);
    }

    static Node *Merge(std::tuple<Node*,Node*,Node*> t) {
        return Merge(std::get<0>(t),Merge(std::get<1>(t),std::get<2>(t)));
    }

    static Node *Kth(Node *pos,int k) {
        while(k) {
            int ls=pos->son[0]->size+1;
            if(k==ls)
                return pos;
            else if(k<ls)
                pos=pos->son[0];
            else {
                k-=ls;
                pos=pos->son[1];
            }
        }
        return 0;
    }

    static int Locate(Node *pos,int v) {
        if(pos==null)
            return 0;
        else if(pos->son[0]->max>v)
            return Locate(pos->son[0],v);
        else {
            int res=pos->son[0]->size;
            if(pos->v<v)
                res+=1+Locate(pos->son[1],v);
            return res;
        } 
    }

    int Kth(int k) {
        return Kth(root,k)->v;
    }

    void Do(int m,int r) {
        Node *rt,*rm,*pl,*pr;
        std::tie(rt,rm)=Split(root,r);
        std::tie(pl,pr)=Split(rt,m);
        rt=null;
        while(pl!=null && pr!=null) {
            int x=Kth(pl,1)->v,y=Kth(pr,1)->v;
            if(x>y) {
                std::swap(pl,pr);
                std::swap(x,y);
            }
            auto r=Split(pl,Locate(pl,y));
            rt=Merge(rt,r.first);
            pl=r.second;
        }
        if(pl==null || pr==null)
            rt=Merge(rt,pl==null?pr:pl);
        root=Merge(rt,rm);
    }

};
Treap::Node *Treap::null=new Treap::Node(malloc(0));

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    freopen("input","r",stdin);
    int n,m;std::cin>>n>>m;
    static int a[XN];
    for(int i=1;i<=n;++i)
        std::cin>>a[i];
    Treap T(a,n);
    for(int i=1;i<=m;++i) {
        int op;std::cin>>op;
        if(op==1) {
            int l,mid,r;std::cin>>l>>mid>>r;
            T.Do(mid,r);
        } else {
            int x;std::cin>>x;
            std::cout<<T.Kth(x)<<'\n';
        }
    }
    return 0;
}

支配树

行吧,**T**出题人逼我学这玩意
先吐个槽,感觉比较少见的模板放在签到|简单题的位置非常不好,容易产生一种奇怪的导向。

有向图的上一堆定义啥来着…

  1. 树边
  2. 前向边::是DFS树中从一个顶点指向该顶点的一个非子顶点后裔的边。
  3. 回边:是DFS树中从一个顶点指向其祖先的边。
  4. 横跨边:既不是从顶点指向其后裔的边,也不是指向其祖先的边;横跨边是从一个顶点指向一个已完全访问过的顶点的边。

定义和记号

  • 固定起点r的有向图中,若r-w的每一条路径都必定经过v\cancel{=} w,则v支配w
  • v支配w,且w的其余支配点全都支配v,则称vw的最近支配点,记为v={\rm idom}(w)
  • 在搜索树T上点w的祖先中,通过非树边可以到达w的深度最小的祖先v,称为w的半必经点。半必经点也是唯一的,记v={\rm sdom}(w),但不一定是必经点。

支配树定理

r外都有唯一\rm idom,且不成环,故所有({\rm idom}(w),w)的边形成一棵树,v支配w当且仅当v是树中w的祖先,这棵树叫支配树。

半必经点定理

对于点w,考虑所有前驱v
1. 若{\rm dfn}(v) < {\rm dfn}(w),则该边为树边或者前向边,找到所有这样的{\rm dfn}(v)中的最小值。
2. 否则,为横跨边或回边,此时\forall u\in v的祖先,找到满足{\rm dfn}(u) > {\rm dfn}(w){\rm dfn}({\rm sdom}(u))的最小值。
两种情况取最小,就是w的半必经点的\rm dfn

必经点定理

对于{\rm sdom}(w)-w路径上的端点之外的点构成的集合P,设vP中半必经点时间戳最小的点。

{\rm idom}(w)=
\left\{
\begin{aligned}
{\rm sdom}(w),&{\rm sdom}(v)= {\rm sdom}(w)\\
{\rm idom}(v),&{\rm sdom}(v)\cancel{=} {\rm sdom}(w)
\end{aligned}
\right.

Lengauer-Tarjan算法

  1. 通过DFS构建搜索树,并计算出每个节点的时间戳。
  2. 根据半必经点定理,按照时间戳从大到小的顺序计算每个节点的半必经节点。
  3. 根据必经点定理,按照时间戳从小到大的顺序,把半必经节点≠必经节点的节点进行修正。

Code


std::vector<int> G[XN]; int idom[XN],sdom[XN],n; void LengauerTarjan(int root) { static std::vector<int> R[XN],dom[XN]; static int dfn[XN],fa[XN],dfs[XN],dsu[XN],min[XN]; int clk=0; static std::function<void(int)> DFS=[&](int pos) { dfs[dfn[pos]=++clk]=pos; for(int u : G[pos]) { R[u].push_back(pos); if(!dfn[u]) { fa[u]=pos; DFS(u); } } }; for(int i=1;i<=n;++i) { idom[i]=dfn[i]=0; dsu[i]=-1; min[i]=sdom[i]=i; R[i]={}; } fa[root]=0; DFS(root); for(int i=clk;i>=2;--i) { int pos=dfs[i],t=clk+1; static std::function<int(int)> Update=[&](int pos)->int { if(dsu[pos]==-1) return pos; else { int rt=Update(dsu[pos]); if(dfn[sdom[min[pos]]]>dfn[sdom[min[dsu[pos]]]]) min[pos]=min[dsu[pos]]; return dsu[pos]=rt; } }; for(int u : R[pos]) if(dfn[u]) { if(dfn[u]<dfn[pos]) Reduce(t,dfn[u]); else { Update(u); Reduce(t,dfn[sdom[min[u]]]); } } dsu[pos]=fa[pos]; dom[sdom[pos]=dfs[t]].push_back(pos); for(int u : dom[fa[pos]]) { Update(u); idom[u]=sdom[min[u]]==sdom[u]?sdom[u]:min[u]; } dom[fa[pos]]={}; } for(int i=2;i<=clk;++i) { int pos=dfs[i]; if(idom[pos]!=sdom[pos]) idom[pos]=idom[idom[pos]]; } }

[HDU6613]Squrirrel

Link

Solution

比较考验实现的树形DP。学习了一下zd的处理方法,以后可以多试一试。

Code

const int XN=2e5+11,INF=1e9;

struct Edge {
    int to,v;
};

int Ans[XN];
std::vector<Edge> G[XN];
std::array<int,2> f[XN],g[XN],h[XN];//f[pos][0/1] 子树 删/不删的最长路径

void DP(int pos,int fa) {
    f[pos][0]=f[pos][1]=0;

    for(Edge &e : G[pos]) {
        int u=e.to;
        if(u!=fa) {
            DP(u,pos);
            Enlarge(f[pos][1],f[u][0]+e.v);
            Reduce(f[pos][1],std::min(std::max(f[pos][0],f[u][1]+e.v),std::max(f[pos][0],f[u][0])));
            Enlarge(f[pos][0],f[u][0]+e.v);
        }
    }

    static std::array<int,2> _pre[XN],*pre=_pre+1,suf[XN];
    pre[-1]=suf[G[pos].size()]={0,0};
    for(size_t i=0;i<G[pos].size();++i)
        if(G[pos][i].to!=fa) {
            int u=G[pos][i].to,v=G[pos][i].v;
            pre[i][0]=std::max(pre[i-1][0],f[u][0]+v);
            pre[i][1]=std::min(std::max(pre[i-1][0],std::min(f[u][0],f[u][1]+v)),
                        std::max(pre[i-1][1],f[u][0]+v));
        } else
            pre[i]=pre[i-1];
    for(int i=G[pos].size()-1;i>=0;--i)
        if(G[pos][i].to!=fa) {
            int u=G[pos][i].to,v=G[pos][i].v;
            suf[i][0]=std::max(suf[i+1][0],f[u][0]+v);
            suf[i][1]=std::min(std::max(suf[i+1][0],std::min(f[u][0],f[u][1]+v)),
                        std::max(suf[i+1][1],f[u][0]+v));
        } else
            suf[i]=suf[i+1];
    for(size_t i=0;i<G[pos].size();++i)
        if(G[pos][i].to!=fa) {
            int u=G[pos][i].to;
            g[u][0]=std::max(pre[i-1][0],suf[i+1][0])+G[pos][i].v;
            g[u][1]=std::min(std::max(pre[i-1][0],suf[i+1][1]),std::max(pre[i-1][1],suf[i+1][0]))+G[pos][i].v;
        }
}

void DFS(int pos,int fa) {
    for(Edge &e : G[pos]) {
        int u=e.to;
        if(u!=fa) {
            h[u][0]=std::max(g[u][0],h[pos][0]+e.v);
            h[u][1]=std::min(std::min(std::max(g[u][1],h[pos][0]+e.v),
                                std::max(g[u][0],h[pos][1]+e.v)),
                                std::max(g[u][0]-e.v,h[pos][0]));
            DFS(u,pos);
        }
    }
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--) {
        int n;std::cin>>n;
        for(int i=1;i<=n;++i)
            G[i].clear();
        for(int i=1;i<=n-1;++i) {
            int x,y,v;std::cin>>x>>y>>v;
            G[x].push_back({y,v});
            G[y].push_back({x,v});
        }

        DP(1,0);
        DFS(1,0);

        for(int i=1;i<=n;++i)
            Ans[i]=std::min(std::max(f[i][0],h[i][1]),std::max(f[i][1],h[i][0]));

        auto it=std::min_element(Ans+1,Ans+1+n);
        std::cout<<(it-Ans)<<' '<<*it<<'\n';
    }
    return 0;
}

A串中不在B中出现的子串计数

后缀数组

A#B建后缀数组,对于所有满足sa[i]<=|A|的后缀,若只考虑受到前面所有后缀的限制,则对答案有|A|-sa[i]+1-height[i]的贡献。
然而后面的后缀也会对它有限制。原则是sa[i]<=|A|的后缀之间前面出现限制后面的,然后sa[i]>|A|的后缀对sa[i]<=|A|的限制可以从后向前。
因此一个后缀的实际贡献就是|A|-sa[i]+1-max(height[i],LCP(sa[i],sa[j])),j=min(j>i,sa[j]>|A|)

后缀自动机

先匹配得到每个节点能够匹配到的最长长度,然后沿着parent树向上更新上去,最后一个节点对答案的贡献为len-max(par->len,match)
NOTE 后缀自动机的遍历一定要写拓扑序!标号的大小关系并不一定是拓扑序的前后关系!
NOTE 要小心SAM里会调用拷贝构造函数!被坑好多次了。

[hdu6592]Beauty Of Unimodal Sequence

Link

第一次写,求方案的时候,大力了一波ST+二分,光荣MLE。

Solution

求出每个位置的后缀单减和单峰答案。
对于单减答案,若前后两个位置答案相同,则前面的数字小于后面的。
对于单峰答案,若前后两个位置答案相同,则前面的数字大于后面的。
由此就可以二分了!
NOTE 在vector二分的时候一定要注意好边界!!

template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}

lower_bound本质上是求不满足comp(val,*it)的第一个it

template <class ForwardIterator, class T>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = std::distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; std::advance (it,step);
    if (!(val<*it))                 // or: if (!comp(val,*it)), for version (2)
      { first=++it; count-=step+1;  }
    else count=step;
  }
  return first;
}

upper_bound本质上是求满足comp(*it,val)的第一个it

Code

#include <bits/stdc++.h>

template <class T>
bool Enlarge(T &a,T const &b) {
    return a<b?a=b,1:0;
}

template <class T>
bool Reduce(T &a,T const &b) {
    return a>b?a=b,1:0;
}

const int XN=3e5+11,INF=1e9;

int bit[XN],bw;
int Query(int pos,int d) {
    int res=0;
    for(;pos && pos<=bw;pos-=d*(pos & -pos))
        Enlarge(res,bit[pos]);
    return res;
}

void Modify(int pos,int v,int d) {
    for(;pos && pos<=bw;pos+=d*(pos & -pos))
        Enlarge(bit[pos],v);
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);
    //freopen("1002.in","r",stdin);
    for(int n;std::cin>>n;) {
        static int a[XN];
        std::vector<int> nums;
        for(int i=1;i<=n;++i) {
            std::cin>>a[i];
            nums.push_back(a[i]);
        }
        a[n+1]=INF;
        a[n+2]=-INF;
        std::sort(nums.begin(),nums.end());
        nums.erase(std::unique(nums.begin(),nums.end()),nums.end());
        for(int i=1;i<=n;++i)
            a[i]=std::lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
        std::fill(bit+1,bit+1+(bw=nums.size()),0);
        //g[i] 以i为开头的最长的带折
        //h[i]           纯下降
        static int h[XN],g[XN];
        for(int i=n;i>=1;--i)
            Modify(a[i],h[i]=Query(a[i]-1,1)+1,1);
        std::fill(bit+1,bit+1+bw,0);
        for(int i=n;i>=1;--i) {
            g[i]=std::max(h[i],Query(a[i]+1,-1)+1);
            Modify(a[i],std::max(g[i],h[i]),-1);
        }
        static std::vector<int> gpos[XN],hpos[XN];
        for(int i=1;i<=n;++i) {
            gpos[i].clear();
            hpos[i].clear();
        }
        for(int i=1;i<=n;++i) {
            gpos[g[i]].push_back(i);
            hpos[h[i]].push_back(i);
        }

        int len=*std::max_element(g+1,g+1+n);

        for(int i=1;i<=len;++i) {
            gpos[i].push_back(n+2);
            hpos[i].push_back(n+1);
        }

        std::vector<int> s1,s2;

        for(int i=1,p=gpos[len].front(),inc=1;i<=len;++i) {
            s1.push_back(p);    
            if(i!=len) {
                int nxt=n+1;
                if(inc) {
                    int t=*std::upper_bound(gpos[len-i].begin(),gpos[len-i].end(),p);
                    if(a[t]>a[p])
                        Reduce(nxt,t);
                }
                int t=*std::upper_bound(hpos[len-i].begin(),hpos[len-i].end(),p);
                if(a[t]<a[p] && Reduce(nxt,t))
                    inc=0;
                p=nxt;
            }
        }

        for(int i=1,p=*std::next(gpos[len].rbegin()),inc=1;i<=len;++i) {
            s2.push_back(p);    
            if(i!=len) {
                int nxt=-1;
                if(inc) {
                    int t=*std::prev(std::upper_bound(gpos[len-i].begin(),gpos[len-i].end(),p,[&](int x,int y)->bool {
                        return a[x]>=a[y];
                    }));
                    if(t>p)
                        Enlarge(nxt,t);
                }
                int t=*std::prev(std::upper_bound(hpos[len-i].begin(),hpos[len-i].end(),p,[&](int x,int y)->bool {
                    return a[x]<=a[y];
                }));
                if(t>p && Enlarge(nxt,t))
                    inc=0;
                p=nxt;
            }
        }

        for(int i=0;i<len;++i)
            std::cout<<s1[i]<<(i+1==len?'\n':' ');
        for(int i=0;i<len;++i)
            std::cout<<s2[i]<<(i+1==len?'\n':' ');
    }
    return 0;
}

[Nowcoder Multi Univerisity Training 3I]Median

Link

Solution

证明:若存在合法方案,则存在合法方案使得a_i\in (b_i,b_{i+1},b_{i+2})
题解给的思路是证明如果a_i\notin (b_{i-2},b_{i-1},b_i),则a_i < \min (b_{i-2},b_{i-1},b_i)a_i > \max (b_{i-2},b_{i-1},b_i)
证明:若a_i\notin (b_{i-2},b_{i-1},b_i),且a_i < b_{i-2}a_i > b_{i-1},则\min(a_{i-1},a_i)=b_{i-2},\max(a_{i-1},a_{i+1})=b_{i-1},与前面b_{i-1} < b_{i-2}矛盾。因此a_ib_{i-2},b_{i-1}的大小关系必然相同。
相反的情况证明是对称的,由此可以得到完整结论。

[Nowcoder Multi Univerisity Training 2G]Polygons

Link

辣鸡题目

Code

const int XN=1e3+11,XV=1e6+11;
const double eps=1e-10,inf=1e10;

int sgn(double const &x) {
    return (x>-eps)-(x<eps);
}

double p2(double const &x) { 
    return x*x;
}

struct Point {
    double x,y;

    double Length() const {
        return sqrt(x*x+y*y);
    }

    Point Normal() const {
        return {-y,x};
    }

    Point Unit() const {
        double len=Length();
        return Point{x/len,y/len};
    }

    friend Point operator +(const Point &a,const Point &b) {
        return {a.x+b.x,a.y+b.y};
    }

    friend Point operator -(const Point &a,const Point &b) {
        return {a.x-b.x,a.y-b.y};
    }

    friend Point operator *(const Point &a,const double &k) {
        return Point{a.x*k,a.y*k};
    }

    friend Point operator /(const Point &a,const double &k) {
        return Point{a.x/k,a.y/k};
    }

    friend double Inner(const Point &a,const Point &b) {
        return a.x*b.x+a.y*b.y;
    }

    friend double Outer(const Point &a,const Point &b) {
        return a.x*b.y-a.y*b.x;
    }
};

struct Line {
    Point p,v;
};

double Dist(const Point &a,const Point &b) {
    return (a-b).Length();
}

double Dist(const Point &a,Line const &l) {
    return fabs(Outer(a-l.p,l.v))/l.v.Length();
}

Point Cross(Line const &l1,Line const &l2) {
    double t=Outer(l2.v,l1.p-l2.p)/Outer(l1.v,l2.v);
    return l1.p+l1.v*t;
}

double cos(Point const &a,Point const &b) {
    return Inner(a,b)/a.Length()/b.Length();
}
int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;
    std::cin>>n;
    std::vector<Line> l;
    for(int i=1;i<=n;++i) {
        Point p1,p2;
        std::cin>>p1.x>>p1.y>>p2.x>>p2.y;
        l.push_back({p1,p2-p1});
    }
    std::vector<Point> cross;
    static std::vector<int> cut[XN];
    for(size_t i=0;i<l.size();++i)
        for(size_t j=i+1;j<l.size();++j)
            if(Outer(l[i].v,l[j].v)!=0) {
                cut[i].push_back(cross.size());
                cut[j].push_back(cross.size());
                cross.push_back(Cross(l[i],l[j]));
            }
    static std::vector<int> G[XV];
    for(size_t i=0;i<l.size();++i) {
        std::sort(cut[i].begin(),cut[i].end(),[&](int x,int y)->bool {
            return Inner(cross[x]-l[i].p,l[i].v)<Inner(cross[y]-l[i].p,l[i].v);
        });
        for(size_t j=0;j+1<cut[i].size();++j) {
            //std::cerr<<i<<' '<<j<<'\n';
            G[cut[i][j]].push_back(cut[i][j+1]);
            G[cut[i][j+1]].push_back(cut[i][j]);
        }
    }
    //一个交点最多4条线啊
    std::vector<double> area;
    for(size_t i=0;i<cross.size();++i)
        while(G[i].size()) {
            Point v=cross[G[i].front()]-cross[i];
            double size=0;
            int pos=G[i].front();
            for(int nxt;G[pos].size();pos=nxt) {
                auto iter=std::find(G[pos].begin(),G[pos].end(),i);
                if(iter!=G[pos].end() && size!=0) {
                    area.push_back(size/=2);
                    G[pos].erase(iter);
                    break;
                } else {
                    iter=std::min_element(G[pos].begin(),G[pos].end(),[&](int x,int y)->bool {
                        double ox=Outer(v,cross[x]-cross[pos]),oy=Outer(v,cross[y]-cross[pos]),
                            cx=cos(v,cross[x]-cross[pos]),cy=cos(v,cross[y]-cross[pos]);
                        if(sgn(ox)<=0 || sgn(oy)<=0)
                            return sgn(ox)>0;
                        else
                            return cx<cy;
                    });
                    if(Outer(v,cross[nxt=*iter]-cross[pos])>0) {
                        size+=Outer(cross[pos]-cross[i],cross[nxt]-cross[i]);
                        G[pos].erase(iter);
                        v=cross[nxt]-cross[pos];
                    } else
                        break;
                }
            }
            G[i].erase(G[i].begin());
        }
    std::sort(area.begin(),area.end(),std::greater<double>());
    std::cout.precision(10);
    std::cout<<area.size()<<' '<<area.front()<<' '<<area.back()<<'\n';
    int m;std::cin>>m;
    while(m--) {
        int k;std::cin>>k;--k;
        if(k>=(int)area.size())
            std::cout<<"Invalid question\n";
        else
            std::cout<<area[k]<<'\n';
    }
    return 0;
}

[Nowcoder Multi Univerisity Training 2J]Subarray

Solution

可能作为区间端点的点个数最多为3e7
f[i]表示以第i个区间右端点为答案右端点的最大区间和
g[i]表示以第i个区间左端点为答案左端点的最大区间和
f[i]=\max(0,f[i−1]−(l[i]−r[i−1]−1))+r[i]−l[i]+1
g[i]=\max(0,g[i+1]−(l[i+1]−r[i]−1))+r[i]−l[i]+1
如果f[i]+g[i+1]≥l[i+1]−r[i]−1,说明答案的左右端点可以跨越[r[i]+1,l[i+1]−1],那么把这些合并考虑
搞完上面,问题就变成了给你若干个长度和不超过3e7的(1,−1)序列,问有多少区间和大于1
然后就好做了