win10 做网站服务器,秦皇岛市住房和城乡建设局官网,合肥网站建设方案咨询,asp门户网站系统*原题链接*
并不是非常难的题#xff0c;不过细节非常多。
首先大题思路很明确#xff0c;把所有条件储存下来#xff0c;把这些l#xff0c;r#xff0c;x啥的离散化#xff0c;然后区间异或#xff0c;最后查询最大值。至于区间异或用差分就好了#xff0c;因为异或…*原题链接*
并不是非常难的题不过细节非常多。
首先大题思路很明确把所有条件储存下来把这些lrx啥的离散化然后区间异或最后查询最大值。至于区间异或用差分就好了因为异或一个数两次等于没异或。
不过就出问题了因为我们在差分操作的时候可能会涉及某些区间的端点为了防止漏掉这些情况就把L-1R1x-1x1都加入离散化数组。
不过最后依然还有细节问题因为我们没考虑0。如果一个区间[l,r]中包含0而我们离散化数组中未加入0值那么就会出错最后喜提WA90。
思路理顺后代码也并不难写。
#includebits/stdc.h
using namespace std;
#define int long long
const int N5e510;//fast read
int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-) f-1;chgetchar();}while(ch0ch9) xx*10ch-0,chgetchar();return x*f;
}int n,lsh[N],tot,cnt,a[N],d[N],w[N],ty[N],l[N],r[N];signed main(){nread();lsh[tot]0;//注意加入0值for(int i1;in;i){ty[i]read();if(ty[i]1){l[i]read(),r[i]read();lsh[tot]l[i],lsh[tot]r[i],lsh[tot]l[i]-1,lsh[tot]r[i]1;}else if(ty[i]2){l[i]read();lsh[tot]l[i],lsh[tot]l[i]-1,lsh[tot]l[i]1;}else{l[i]read();lsh[tot]l[i],lsh[tot]l[i]-1,lsh[tot]l[i]1;}w[i]read();}sort(lsh1,lsh1tot),cntunique(lsh1,lsh1tot)-lsh-1;for(int i1;in;i) l[i]lower_bound(lsh1,lsh1cnt,l[i])-lsh;//离散化//处理询问for(int i1;in;i){if(ty[i]1){r[i]lower_bound(lsh1,lsh1cnt,r[i])-lsh;d[l[i]]^w[i],d[r[i]1]^w[i];}else if(ty[i]2){d[l[i]]^w[i],d[l[i]1]^w[i];}else{d[1]^w[i],d[l[i]]^w[i],d[l[i]1]^w[i];}}//查询int ansd[1],pos1;for(int i2;icnt;i){d[i]^d[i-1];if(d[i]ans) ansd[i],posi;else if(d[i]ansabs(lsh[i])abs(lsh[pos])) posi;}coutans lsh[pos]endl;return 0;
}