CF1860F 题解

__vector__ · 2023-10-04 16:30:21 · 个人记录

点积是 (a_i \cdot x + b_i \cdot y)，变为 y(a_i \cdot \frac{x}{y} + b_i)，设 K = \frac{x}{y}然后把 K 去掉进行排序。

然后按照 K=0 排序得到一个初始数组。

然后计算出所有点对 (c,d) 的 k 值（c 小于 d），使得当 K = k 时，初始数组第 c 个三元组的值开始超过初始数组第 d 个。

然后枚举每个 K = k_i。

题解剩下的部分见这里

代码（我相信没人读懂，其中 unordered_map 使用的 pair<int,int> 哈希使用了知乎上的代码）：

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
const double eps=1e-18;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
/*
此程序 pair hash 模板转载信息：  
作者：youngforest
链接：https://www.zhihu.com/question/30921173/answer/1248680260
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
template <typename T>
inline void hash_combine(std::size_t &seed, const T &val) {
    seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// auxiliary generic functions to create a hash value using a seed
template <typename T> inline void hash_val(std::size_t &seed, const T &val) {
    hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {
    hash_combine(seed, val);
    hash_val(seed, args...);
}

template <typename... Types>
inline std::size_t hash_val(const Types &... args) {
    std::size_t seed = 0;
    hash_val(seed, args...);
    return seed;
}

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2> &p) const {
        return hash_val(p.first, p.second);
    }
};
const int maxn = 3005;
int t, n;
struct Bracket
{
    int a, b;
    int contri;
} bracket[maxn];
struct SegmentTree
{
    int L[maxn << 2], R[maxn << 2];
    int val[maxn << 2];
    int premin[maxn << 2]; // 前缀最小值
    int len(int pos)
    {
        return R[pos] - L[pos] + 1;
    }
    void pushup(int pos)
    {
        val[pos] = val[pos << 1] + val[pos << 1 | 1];
        premin[pos] = min(premin[pos << 1], val[pos << 1] + premin[pos << 1 | 1]);
    }
    void chg(int pos, int x, int _val)
    {
        if (L[pos] > x || R[pos] < x)
            return;
        if (L[pos] == x && x == R[pos])
        {
            val[pos] += _val;
            premin[pos] = val[pos]; // 注意不能直接加上 _val，因为 premin[pos] 可能此前没有定义（即 premin[pos]=1e9）
            return;
        }
        int mid = L[pos] + R[pos] >> 1;
        if (mid >= x)
            chg(pos << 1, x, _val);
        if (mid < x)
            chg(pos << 1 | 1, x, _val);
        pushup(pos);
    }
    void build(int pos, int l, int r)
    {
        L[pos] = l, R[pos] = r;
        val[pos] = 0;
        premin[pos] = 1e9;
        if (l == r)
            return;
        int mid = l + r >> 1;
        build(pos << 1, l, mid);
        build(pos << 1 | 1, mid + 1, r);
    }
} SGT;
struct SWAP
{
    int l, r;
    double k;
} sw[maxn*maxn];
int top;
int rk[maxn]; // 首次排序中第 i 个点，现在排名
struct UnionSet
{
    int fa[maxn];
    int find(int x)
    {
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
    void un(int a,int b)
    {
        int r1=find(a),r2=find(b);
        if(r1==r2)return;
        fa[r1]=r2;
    }
    void init()
    {
        for(int i=1;i<=2*n;i++)fa[i]=i;
    }
}us;
vector<short> rem[maxn],rem2[maxn];
vector<short> wait,val2,old1,old2;
unordered_map<pair<short,short>,vector<short>,pair_hash > cnt;// 每种节点的个数（主意不是交换）
bitset<maxn> vis;
vector<short> thrower,able;
queue<pii> q;
int main()
{
    scanf("%d", &t);
    FOR(_,1,t)
    {
        scanf("%d", &n);
        FOR(i, 1, 2 * n)
        {
            scanf("%d%d", &bracket[i].a, &bracket[i].b);
            char c = getchar();
            while (c != '(' && c != ')')
                c = getchar();
            if (c == '(')
                bracket[i].contri = 1;
            else
                bracket[i].contri = -1;
        }
        us.init();
        // 现在按照 (a*x + b*y)/y = a*(x/y) + b 排序，设 k = x/y
        // 则按照 a*k + b 排序
        sort(bracket + 1, bracket + 2 * n + 1, [&](Bracket &a, Bracket &b)
             {
        if(a.b!=b.b)return a.b<b.b;
        else if(a.a!=b.a)return a.a<b.a;
        else return a.contri>b.contri; }); // 将所有点对按照 k=0 排序，若权值相同，左括号优先。
        SGT.build(1, 1, 2 * n);
   //     puts("========");
        FOR(i, 1, 2 * n)
        {
//printf("%d %d %d\n",bracket[i].a,bracket[i].b,bracket[i].contri);
            rk[i] = i;
          //  printf("ith.brack = %d\n",bracket[i].contri);
            SGT.chg(1, i, bracket[i].contri);
            FOR(j, i + 1, 2 * n)
            {
                if(bracket[i].a<=bracket[j].a)continue;
                double k = double(bracket[j].b - bracket[i].b) / double(bracket[i].a - bracket[j].a);
                if (k <= 1e-18)
                    continue; // 由于是 ka+b，在 b 落后的情况下想要反超只能靠 ka

                sw[++top] = {i, j, k};
       //         printf("provide: %d & %d can swap when k = %.5lf\n",i,j,k);
            }
        }
        bool ok=(SGT.premin[1]==0);
        assert(SGT.val[1]==0);
       // printf("premin = %d\n",SGT.premin[1]);
        sort(sw + 1, sw + top + 1, [&](SWAP &a, SWAP &b){return a.k<b.k;});
       // printf("number of swaps: %d\n",top);
        FOR(i, 1, top)
        {
         //   printf("i = %d k = %.5lf\n",i,sw[i].k);
            int j=i;

            wait.clear();
            val2.clear();
            old1.clear();
            old2.clear();
            cnt.clear();
            vis.reset();
            wait.emplace_back(sw[j].l);// wait: 待排序的节点列表
            wait.emplace_back(sw[j].r);// 所有节点原来的 rank 列表
            val2.emplace_back(rk[sw[j].l]);
            val2.emplace_back(rk[sw[j].r]);
            cnt[make_pair(bracket[sw[j].l].a,bracket[sw[j].l].b)].emplace_back(sw[j].l);
            vis[sw[j].l]=1;
            if(!vis[sw[j].r])cnt[make_pair(bracket[sw[j].r].a,bracket[sw[j].r].b)].emplace_back(sw[j].r);
            vis[sw[j].r]=1;
            us.un(sw[j].l,sw[j].r);
          //  printf("start from  %d and k = %.5lf\n",i,sw[j].k);
       //     printf("swap = %d %d\n",sw[j].l,sw[j].r);
            while(j<top&&abs(sw[j+1].k-sw[j].k)<=eps)
            {
                j++;
                if(!vis[sw[j].l])cnt[make_pair(bracket[sw[j].l].a,bracket[sw[j].l].b)].emplace_back(sw[j].l);
                vis[sw[j].l]=1;
                if(!vis[sw[j].r])cnt[make_pair(bracket[sw[j].r].a,bracket[sw[j].r].b)].emplace_back(sw[j].r);
                vis[sw[j].r]=1;
                wait.emplace_back(sw[j].l);
                wait.emplace_back(sw[j].r);
                val2.emplace_back(rk[sw[j].l]);
                val2.emplace_back(rk[sw[j].r]);
           //     printf("swap = %d %d\n",sw[j].l,sw[j].r);
                us.un(sw[j].l,sw[j].r);
            }
            old1=wait;
            old2=val2;

            thrower.clear();
            able.clear();
            for(int i=0;i<wait.size();i++)
            {
                rem[us.find(wait[i])].emplace_back(wait[i]);
                rem2[us.find(wait[i])].emplace_back(val2[i]);
                thrower.emplace_back(wait[i]);
                able.emplace_back(us.find(wait[i]));
            }
            sort(able.begin(),able.end());
            int sz=unique(able.begin(),able.end())-able.begin()-1;
            while(able.size()>sz+1)able.pop_back();
            for(int v:able)
            {
                //printf("")
                sort(rem[v].begin(),rem[v].end());
                int siz=unique(rem[v].begin(),rem[v].end())-rem[v].begin()-1;
                while(rem[v].size()>siz+1)rem[v].pop_back();
                sort(rem[v].begin(),rem[v].end(),[&](int a,int b){
                     return bracket[a].contri>bracket[b].contri;});
                sort(rem2[v].begin(),rem2[v].end());
                unique(rem2[v].begin(),rem2[v].end());
                while(rem2[v].size()>siz+1)rem2[v].pop_back();
                for(int k=0;k<rem[v].size();k++)
                {
                    SGT.chg(1,rk[rem[v][k]],-bracket[rem[v][k]].contri);
                    rk[rem[v][k]]=rem2[v][k];
           //         printf("chg [%d] = %d\n",rem[v][k],rem2[v][k]);
                    SGT.chg(1,rk[rem[v][k]],bracket[rem[v][k]].contri);
                }
            }
            for(int v:able)rem[v].clear(),rem2[v].clear();
            for(int v:thrower)us.fa[v]=v;
         //   puts("????????");
        //    printf("up to %d\n",j);
     /*   printf("fix up when %d to %d th: \n",i,j);
            FOR(k,1,n*2)
            {
                printf("rk[%d] = %d\n",k,rk[k]);
            }*/
            if(SGT.premin[1]==0)
            {
                ok=1;
                break;
            }
            for(int k=0;k<old1.size();k++)
            {
                SGT.chg(1,rk[old1[k]],-bracket[old1[k]].contri);
                rk[old1[k]]=old2[k];
                SGT.chg(1,rk[old1[k]],bracket[old1[k]].contri);
            }// clear
           /*  printf("preclear: \n");
            FOR(k,1,n*2)
            {
                printf("rk[%d] = %d\n",k,rk[k]);
            }*/
         //   printf("fix up: %d\n",SGT.premin[1]);
            for(int k=i;k<=j;k++)
            {
                sort(cnt[make_pair(bracket[sw[k].l].a,bracket[sw[k].l].b)].begin(),cnt[make_pair(bracket[sw[k].l].a,bracket[sw[k].l].b)].end(),[&](int a,int b){
                     return bracket[a].contri>bracket[b].contri;});
                sort(cnt[make_pair(bracket[sw[k].r].a,bracket[sw[k].r].b)].begin(),cnt[make_pair(bracket[sw[k].r].a,bracket[sw[k].r].b)].end(),[&](int a,int b){
                     return bracket[a].contri>bracket[b].contri;});
            }
            for(int k=i;k<=j;k++)
            {
                int l = sw[k].l, r = sw[k].r;
           //     printf("nwswp = %d %d\n",l,r);
          /*
                if(cnt[make_pair(bracket[l].a,bracket[l].b)].size()>1)
                {
                    l=cnt[make_pair(bracket[l].a,bracket[l].b)].back();
                }
                if(cnt[make_pair(bracket[r].a,bracket[r].b)].size()>1)
                {
                    r=cnt[make_pair(bracket[r].a,bracket[r].b)].front();
                }*/
                if (rk[l] > rk[r])
                    continue;
             //   printf("swap: %d %d\n",l,r);
                SGT.chg(1,rk[l],-bracket[l].contri);
                SGT.chg(1,rk[r],-bracket[r].contri);
                swap(rk[l],rk[r]);
                SGT.chg(1,rk[l],bracket[l].contri);
                SGT.chg(1,rk[r],bracket[r].contri);
                assert(SGT.val[1]==0);
            }
            vis.reset();
            while(!q.empty())q.pop();
            for(int k=i;k<=j;k++)
            {
                if(!vis[sw[k].l])
                {
                    auto temp=make_pair(bracket[sw[k].l].a,bracket[sw[k].l].b);
                    q.push(temp);
                    vis[sw[k].l]=1;
                }
                if(!vis[sw[k].r])
                {
                    auto temp=make_pair(bracket[sw[k].r].a,bracket[sw[k].r].b);
                    q.push(temp);
                    vis[sw[k].r]=1;
                }
            }
            while(!q.empty())
            {
                pii u=q.front();
                q.pop();
                vector<int> rkrem;
                for(int v:cnt[u])
                {
                    rkrem.emplace_back(rk[v]);
                }
                sort(rkrem.begin(),rkrem.end());
                for(int i=0;i<cnt[u].size();i++)
                {
                    int v=cnt[u][i];
                    SGT.chg(1,rk[v],-bracket[v].contri);
                    rk[v]=rkrem[i];
                    SGT.chg(1,rk[v],bracket[v].contri);
                }
            }
            if(SGT.premin[1]==0)
            {
                ok=1;
                break;
            }
            i=j;
          /*  printf("after %d th: \n",i);
            FOR(j,1,n*2)
            {
                printf("rk[%d] = %d\n",j,rk[j]);
            }*/
        }
        if(ok)puts("YES");
        else puts("NO");
        top=0;
    }

    return 0;
}