Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<set>
- #include <unordered_set>
- #include <unordered_map>
- #include<map>
- #include<list>
- #include<iomanip>
- #include<cmath>
- #include<string>
- #include<vector>
- #include<queue>
- #include<stack>
- #include<complex>
- #include<sstream>
- #include<iostream>
- #include<fstream>
- #include<algorithm>
- #include<numeric>
- #include<utility>
- #include<functional>
- #include<stdio.h>
- #include<assert.h>
- #include<memory.h>
- #include<bitset>
- #include<math.h>
- #include <string.h>
- #include <strings.h>
- #define f first
- #define s second
- #define mp make_pair
- #define pb push_back
- #define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
- #define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
- #define clr(a,b) memset(a,b,sizeof a)
- #define all(v) v.begin(),v.end()
- #define println(a) cout <<(a) <<endl
- #define sz(x) ((int)(x).size())
- #define readi(x) scanf("%d",&x)
- #define read2i(x,y) scanf("%d%d",&x,&y)
- #define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
- #define readll(x) scanf("%I64d",&x)
- #define mod 1000000007
- #define eps 1e-10
- #define infi 1000000000ll
- #define infll 1000000000000000000ll
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<ll> vll;
- typedef set<int> si;
- typedef unordered_set<int> usi;
- typedef map<int,int> mii;
- typedef map<ll,ll> mll;
- typedef unordered_map<ll,ll> umll;
- const int N = 250005 , A = 50002 , BLOCK_SIZE = 502;
- int n,q,a[N],tree[BLOCK_SIZE][A],treeTemp[A];
- void update(int i,int diff,int tree[]) {
- while(i<A) tree[i] += diff , i += i&-i;
- }
- int getSum(int i,int tree[]) {
- int ret = 0;
- while (i > 0) ret += tree[i] , i -= i&-i;
- return ret;
- }
- int main(){
- scanf("%d",&n);
- lp(i, 1, n) scanf("%d",&a[i]) ,update(a[i],1,tree[i/BLOCK_SIZE]);
- ll ans = 0;
- lpd(i, n, 1)
- ans += getSum(a[i]-1, treeTemp),update(a[i], 1, treeTemp);
- scanf("%d",&q);
- lp(i, 1, q) {
- int x,y;
- scanf("%d%d",&x,&y);
- pll prev,cur;
- int blk_num = x/BLOCK_SIZE;
- lp(i, 0, blk_num-1)
- prev.f += getSum(A-2, tree[i])-getSum(a[x], tree[i]) , cur.f += getSum(A-2, tree[i])-getSum(y, tree[i]);
- lp(i, blk_num+1, n/BLOCK_SIZE)
- prev.s += getSum(a[x]-1, tree[i]) , cur.s += getSum(y, tree[i]);
- lp(i, blk_num*BLOCK_SIZE, x-1) prev.f += a[i]>a[x] , cur.f += a[i] > y;
- lp(i, x+1, min((blk_num+1)*BLOCK_SIZE-1,n)) prev.s += a[x]>a[i] , cur.s += y>a[i];
- ans += cur.f-prev.f+cur.s-prev.s;
- update(a[x],-1,tree[x/BLOCK_SIZE]);
- update(y,1,tree[x/BLOCK_SIZE]);
- a[x] = y;
- printf("%lld\n",ans);
- }
- return 0;
- }
- /*
- */
- //ios::sync_with_stdio(0);cin.tie(0);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement