360笔试9.9

360笔试第一题： 一个数组，对前m个元素进行一系列升序或者降序排序后求现在数组
我想了半天 怎么优化 实在想不出来 直接摁排序，竟然过了。。。就不写代码了

360笔试第二题： 黑白棋， n个数组，每次反转【l，r】闭区间内的元素，问每次翻转后有多少个黑色
我最开始想用线段树但感觉空间复杂度过高；于是就用的队列+merge的想法，但是情况考虑的话比较复杂，最后没有写完。。。希望大佬们可以一起讨论一下呜呜

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <queue>
using namespace std;

//代表为白棋子的区间
struct Node
{
    int l, r;
    Node *next;
    Node(int l_, int r_) : l(l_), r(r_) {}
};

int main()
{
    int n, m;
    cin >> n >> m;
    int l, r;
    Node *head = nullptr;
    Node *now = nullptr, *pre = nullptr;
    //白棋的个数
    int count = 0;
    for (int i = 0; i < m; i++)
    {
        cin >> l >> r;
        pre = nullptr;
        now = head;
        while (now && l <= r)
        {
            // （） 插入的区间l，r， 【】当遍历的区间 now
            // () []
            if (r < now->l)
            {
                break;
            }
            //(  [  )  ]
            else if (l < now->l && r >= now->l && r <= now->r)
            {
                count -= r - now->l + 1;
                int tmp = now->l;
                now->l = r + 1;
                r = tmp - 1;
                if (now->l > now->r)
                {
                    if (pre)
                        pre->next = now->next;
                    Node *temp = now->next;
                    delete now;
                    now = temp;
                }
                break;
            }
            //[  (  )]
            else if (l >= now->l && r <= now->r)
            {
                count -= r - l + 1;
                int tmp = now->l;
                now->l = r + 1;
                r = l - 1;
                l = tmp;
                if (now->l > now->r)
                {
                    if (pre)
                        pre->next = now->next;
                    Node *temp = now->next;
                    delete now;
                    now = temp;
                }
                break;
            }
            //[ (]  )
            else if (l >= now->l && l <= now->r && r > now->r)
            {
                count -= now->r - l + 1;
                int tmp = now->r;
                now->r = l - 1;
                l = tmp + 1;
                if (now->l > now->r)
                {
                    if (pre)
                        pre->next = now->next;
                    Node *temp = now->next;
                    delete now;
                    now = temp;
                }
                else
                {
                    pre = now;
                    now = now->next;
                }
            }
            //(  []  )
            else if (l < now->l && r > now->r)
            {
                count -= now->r - now->l + 1;
                int tmp_r = now->r;
                now->r = now->l - 1;
                now->l = l;
                l = tmp_r + 1;
                pre = now;
                now = now->next;
            }
            //[] ()
            else if (l > now->r)
            {
                pre = now;
                now = now->next;
            }
        }
        if (l <= r)
        {
            Node *temp = new Node(l, r);
            if (pre == nullptr)
            {
                temp->next = now;
                head = temp;
            }
            else
            {
                pre->next = temp;
                temp->next = now;
            }
            count += r - l + 1;
        }
        cout << n - count << endl;
    }

    while (head)
    {
        Node *temp =head;
        head = head->next;
        delete temp;
    }

    return 0;
}

笔试又要挂喽。。。

#360##笔试##笔试凉经#