P6627 题解

· · 题解

第一次见到这么水的省选联考题！！qwq

思路

这道题的思路很显然，就是维护一个值域，值域上面每一个点表示：n 个操作中，所有包含这个点的操作的 w 的异或和。

其实想到这里就差不多是正解了，只是值域比较大，需要进行处理。我们考虑用“扫描线”的思想。

把所有的操作放到数轴上，按照下标进行排序，显然相邻两个操作之间的所有数的值是相同的。因此我们直接用一个点表示这一个区间即可。那么这些点的总和量级是多大呢？O(n)。又因为只有一次询问，所以扫一遍即可。

具体的实现细节：我们考虑用一个结构体 a\{x,w\} 表示：值为 x 的位置需要异或上 w。那么，对于三种操作显然可以轻松用类似差分的方式来实现，即在开头插入一个运算，末尾插入这个运算的逆运算。而异或的逆运算其实就是异或，所以我们在开头和结尾分别插入一个异或即可。

  1. 对于 op=1，我们插入两个结构体 \{l,w\} 和 \{r+1,w\}，这样，进行到 l 的时候，就可以异或一次 w，直到 [l,r] 的区间结束，我们在 r+1 又异或一次 w 抵消了，于是就不会对后续的答案造成影响。

  2. 对于 op=2，我们直接特化成 l=1,r=l 的情况，看成区间，按照 1 操作处理即可。

  3. 对于 op=3，我们看成两个区间 [-\operatorname{INF},y-1] 和 [y+1,\operatorname{INF}]，按照 1 操作处理即可。

于是我们顺利的完成了修改操作。接下来是扫描线：

  1. 如果当前的 x 和上一个 x 相等，那么我们应该一起处理，毕竟同一个位置的操作不可能拆成两次。

  2. 如果当前的异或和 now 比最大值大，我们应当果断替换；否则还要判断相等的情况，取绝对值更小的。绝对值相等还要判断值更大的（即正数那个）。

然后就基本完成了这道题。记得开 long long 并且把最大值和最小值弄得更大 / 更小！我 WA 成 80 分的时候，找了半天才找出来原来是没开 long long 见祖宗了。

时间复杂度 O(n \log n)，瓶颈在排序。理论用基数排序可以做到 O(n) 的线性复杂度。不知道为啥数据只出到 10^5……

顺便吐槽一下数据太水了，我没判断绝对值相等的时候取值更大的但是水过去了（

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=100005;
const int INF=1145141919810;
struct Node{
    int x,w;
    const bool operator<(const Node &o)const{
        return x<o.x;
    }
}a[MAXN<<2]; // 记得四倍空间！
int calc(int L,int R){ // 返回 [L,R] 中最接近 0 的数
    if(L<0 && R<0) return R;
    if(L>0 && R>0) return L;
    return 0;
}signed main(){
    int n,cnt=0; cin>>n;
    for(int i=1;i<=n;i++){
        int op,x,y,w; cin>>op;
        if(op==1){
            cin>>x>>y>>w;
            a[++cnt]=(Node){x,w};
            a[++cnt]=(Node){y+1,w};
        }else if(op==2){
            cin>>x>>w;
            a[++cnt]=(Node){x,w};
            a[++cnt]=(Node){x+1,w};
        }else{
            cin>>y>>w;
            a[++cnt]=(Node){-INF,w};
            a[++cnt]=(Node){y,w};
            a[++cnt]=(Node){y+1,w};
            a[++cnt]=(Node){INF,w};
        }
    }sort(a+1,a+1+cnt);
    int maxn=-INF,now=0,L,R;
    for(int i=1;i<=cnt;){
        int tmp=i;
        while(a[tmp].x==a[i].x) now^=a[tmp].w,tmp++; // 对相同的位置要一次处理掉
        if(now>maxn){ // 如果大于最大值，果断替换
            maxn=now;
            L=a[i].x;
            R=a[tmp].x-1;
        }else if(now==maxn){ // 如果相等，要判断一下其他条件
            int t1=abs(calc(a[i].x,a[tmp].x-1)); // 记得加绝对值！
            int t2=abs(calc(L,R));
            if(t1<t2) L=a[i].x,R=a[tmp].x-1; // 如果绝对值更小，果断替换
            else if(t1==t2 && calc(a[i].x,a[tmp].x-1)!=calc(L,R)) // 绝对值一样，判断哪个值更大
                if(calc(L,R)<0) L=a[i].x,R=a[tmp].x-1; // 如果原来的值小于 0 那么当前的值一定不会更劣，直接替换即可
        }i=tmp; // 向后跳
    }cout<<maxn<<" "<<calc(L,R); // 输出
    return 0;
}