题目连接
题目大意:
就是给你两个长度为nnn的a,ba,ba,b数组,给你q∈[1,1e5]q\in[1,1e5]q∈[1,1e5]次询问,每次询问一个区间[l,r][l,r][l,r]
你对这个区间里面的数可以进行一下操作
取出偶数个位置
l≤pos1<pos2<....<posz≤r∣[z%2==0]l\leq pos_1<pos_2<....<pos_z\leq r|[z\%2==0]l≤pos1<pos2<....<posz≤r∣[z%2==0]
对于里面pos1,pos3,pos5...,posz−1pos_1,pos_3,pos_5...,pos_{z-1}pos1,pos3,pos5...,posz−1的aaa数组位置的数+1+1+1
对于其他位置的bbb数组的位置+1+1+1
就是偶数对bbb操作,奇数对aaa操作
query:query:query:最小操作使得ai=bi∣i∈[l,r]a_i=b_i|i\in[l,r]ai=bi∣i∈[l,r]
不满足输出−1-1−1
解题思路:
思路特别妙:就是我们先构造sub[i]=a[i]−b[i]∣i∈[l,r]sub[i]=a[i]-b[i]|i\in[l,r]sub[i]=a[i]−b[i]∣i∈[l,r]
如果a[i]+1a[i]+1a[i]+1那么sub[i]+1sub[i]+1sub[i]+1,如果b[i]+1b[i]+1b[i]+1,那么sub[i]−1sub[i]-1sub[i]−1
那么我们就把posi,posjpos_i,pos_jposi,posj看成一对操作分别对a,ba,ba,b操作那么就是有点像差分了对于sub数组sub数组sub数组
那么我们考虑最终状态那么就是每个位置subsubsub都是000
但是问题转化到这里最小操作还是不好求因为我们知道对于一对操作中间是不予许交叉的,就是必须连续。
但是我们可以知道一个−1-1−1的条件就是∑i=lrsub[i]!=0∣+1,−1和是不会变的\sum_{i=l}^rsub[i]!=0|+1,-1和是不会变的∑i=lrsub[i]!=0∣+1,−1和是不会变的
那么我们可以对subsubsub求一个前缀和s[i]s[i]s[i]:把差分变成连续操作:区间加区间加区间加
那么:
AC code
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = 2e5 + 10;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {read(first);read(args...);
}
int arr[maxn], brr[maxn];
ll pre[maxn];
int lg[maxn]={-1};
ll STmax[30][maxn];
ll STmin[30][maxn];inline void init(int n) {for(int i = 1; i <= lg[n]; ++ i) {for(int j = 1; j + (1 << i) - 1 <= n; ++ j) {STmax[i][j] = max(STmax[i-1][j],STmax[i-1][j+(1<<(i-1))]);STmin[i][j] = min(STmin[i-1][j],STmin[i-1][j+(1<<(i-1))]);}}
}
inline ll getmax(int l, int r){int len = lg[r-l+1];return max(STmax[len][l],STmax[len][r-(1<<len)+1]);
}inline ll getmin(int l, int r){int len = lg[r-l+1];return min(STmin[len][l],STmin[len][r-(1<<len)+1]);
}int main() {IOS;int T;// cin >> T;T = 1;while(T --) {int n, m;cin >> n >> m;for(int i = 1; i <= n; ++ i) cin >> arr[i];for(int i = 1; i <= n; ++ i) {lg[i] = lg[i/2] + 1;int x;cin >> x;pre[i] = pre[i-1] + arr[i] - x;// cout << pre[i] << " ";STmax[0][i] = pre[i];STmin[0][i] = pre[i];}// cout << endl;init(n);// cout << STmax[2][0] << " ";// cout << getmax(2,6) << endl;while(m --) {int l, r;cin >> l >> r;if(pre[r]-pre[l-1] != 0) cout << "-1\n";else if(getmax(l,r) > pre[l-1]) cout << "-1\n";else cout << pre[l-1] - getmin(l,r) << "\n";}}return 0;
}