题目传送门:http://pan.baidu.com/s/1hsLh92W
OJ传送门:http://oi.cdshishi.net:8080/Problem/1713
这一道题目,考试的时候,想了一个小时,完全没有思路,最后搞了30分的暴力QAQ
考试的时候一直在想如何将更改操作应用于硬币上
然而std是用硬币去操作中查询
为什么考试的时候没有想到呢?考试的时候是想到这样反向来搞的,但因为精神不好+懒所以没有深入思考
所以该睡的觉还是要睡的,该开的黑还是要开的
来说一说std的做法:
设一个硬币,比较大的值为mx,较小的值为mn。操作的阈值为v
则操作可以分为3类
1.mn < v
2.mn <= v < mx
3.mx <= v
对于第一类,明显不影响
对于第二类,明显是不管之前状态如何,全部变为mx
对于第三类,就是直接反转
所以我们可以找到最后一个第二类操作,然后查找之后有多少个三类操作即可
至于代码实现方面,我后来写的是BIT+线段树
std是二维线段树
我的要快一点,std空间要少很多,所以还是把std贴出来吧(std建树的时候有一点奇技淫巧)
std:http://paste.ubuntu.com/19496714/
my code:
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
const int MAXN = 100000+9;
int n,m,arr[MAXN],rev[MAXN],val[MAXN],hash[MAXN*3],tot,MX;
vector<int> G[MAXN]; LL vout;
inline int read(){
char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}
namespace Chair_Tree{
#define CT Chair_Tree
#define lowbit(x) ((x)&-(x))
#define N 10000000
int cnt,ch[N][2],sum[N],ans_tmp;
int q1[MAXN],q2[MAXN],root[MAXN*3];
void modify(int &w, int l, int r, int val, int del){
if (!w) w = ++cnt; sum[w] += del;
if (l < r) {
int mid = (l + r + 1) / 2;
if (val < mid) modify(ch[w][0],l,mid-1,val,del);
else modify(ch[w][1],mid,r,val,del);
}
}
inline void modify(int pos, int val, int del){
for (int i=val;i<=tot;i+=lowbit(i))
modify(root[i],1,m,pos,del);
}
void query(int w, int l, int r, int lim, int rim){
if (lim <= l && r <= rim) ans_tmp += sum[w];
else {
int mid = (l + r + 1) / 2;
if (lim < mid) query(ch[w][0],l,mid-1,lim,rim); if (rim >= mid) query(ch[w][1],mid,r,lim,rim);
}
}
inline int query(int pos, int l, int r){
ans_tmp = 0;
for (int i=pos;i;i-=lowbit(i))
query(root[i],1,m,l,r);
return ans_tmp;
}
inline int GetMX(int L, int R) {
int t1=0,t2=0,l=1,r=m,mid,tmp=0;
for (int i=R;i;i-=lowbit(i)) q1[++t1] = root[i];
for (int i=L;i;i-=lowbit(i)) q2[++t2] = root[i];
for (int i=1;i<=t1;i++) tmp += sum[q1[i]];
for (int i=1;i<=t2;i++) tmp -= sum[q2[i]];
if (!tmp) return 0;
else while (l < r) {
mid = (l + r + 1) / 2; tmp = 0;
for (int i=1;i<=t1;i++) tmp += sum[ch[q1[i]][1]];
for (int i=1;i<=t2;i++) tmp -= sum[ch[q2[i]][1]]; if (tmp > 0) {
l = mid;
for (int i=1;i<=t1;i++) q1[i] = ch[q1[i]][1];
for (int i=1;i<=t2;i++) q2[i] = ch[q2[i]][1];
} else {
r = mid - 1;
for (int i=1;i<=t1;i++) q1[i] = ch[q1[i]][0];
for (int i=1;i<=t2;i++) q2[i] = ch[q2[i]][0];
}
} return l;
}
};
inline int find(int w){
int l=1,r=tot,mid;
while (l <= r) {
mid = (l + r) / 2;
if (hash[mid] < w) l = mid+1; else if (hash[mid] > w) r = mid-1;
else return mid;;
}
}
int main(){
freopen("name.in","r",stdin);
freopen("name.out","w",stdout);
n = read();
for (int i=1;i<=n;i++) arr[i] = hash[++tot] = read();
for (int i=1;i<=n;i++) rev[i] = hash[++tot] = read();
m = read();
for (int i=1,a,b,c;i<=m;i++)
a = read(), b = read(), val[i] = hash[++tot] = read(),
G[a].push_back(i), G[b+1].push_back(-i);
sort(hash+1,hash+1+tot);
tot = unique(hash+1,hash+tot+1)-hash-1;
for (int i=1;i<=n;i++) arr[i] = find(arr[i]);
for (int i=1;i<=n;i++) rev[i] = find(rev[i]);
for (int i=1;i<=m;i++) val[i] = find(val[i]);
for (int k=1;k<=n;k++) {
for (int i=0;i<(int)G[k].size();i++) { if (G[k][i] > 0) CT::modify(G[k][i],val[G[k][i]],1);
else CT::modify(-G[k][i],val[-G[k][i]],-1);
}
int l=1,r=m,ans=0,mn=min(arr[k],rev[k]),mx=max(arr[k],rev[k]);
ans = CT::GetMX(mn-1,mx-1);
if (ans) {
int tmp = CT::query(tot,ans,m) - CT::query(mx-1,ans,m);
if (tmp % 2) vout += (LL)hash[mn];
else vout += (LL)hash[mx];
} else {
int tmp = CT::query(tot,0,m) - CT::query(mx-1,0,m);
if (tmp % 2) vout += (LL)hash[rev[k]];
else vout += (LL)hash[arr[k]];
}
}
printf("%lld\n",vout);
return 0;
}