Hướng dẫn giải của Dãy nghịch thế
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <cstdio> using namespace std; int f[60600]; int main() { int n,x,ans=0; cin >> n; while (n--) { scanf("%d",&x); for (int i=x+1;i<=60000;i+=i&-i) ans+=f[i]; for (int i=x;i;i-=i&-i) f[i]++; } cout << ans << endl; }
Code mẫu của happyboy99x
import java.io.BufferedReader; import java.io.InputStreamReader; public class Main implements Runnable { private static final int MAXVAL = 60000; private int tree[] = new int[MAXVAL+5], a[], n; public void run() { try { BufferedReader inp = new BufferedReader(new InputStreamReader(System.in)); a = new int[n = Integer.parseInt(inp.readLine())]; for( int i = 0; i < n; update(1, a[i++] = Integer.parseInt(inp.readLine()))); int res = 0; for( int i = 0; i < n; i++ ) { res += read(a[i]-1); update(-1, a[i]); } System.out.println(res); inp.close(); } catch (Exception e) { e.printStackTrace(); } } private void update( int val, int idx ) { for(;idx <= MAXVAL; idx += (idx & -idx)) tree[idx] += val; } private int read( int idx ) { int sum = 0; for(; idx > 0; idx -= (idx & -idx)) sum += tree[idx]; return sum; } public static void main(String argv[]) { new Main().run(); } }
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> const int N = 60006; using namespace std; int a[N], tmp[N]; int n; int cal(int l, int r) { if (l == r) return 0; int mid = l + r >> 1; int ans = cal(l, mid) + cal(mid + 1, r); int i = l, j = mid + 1, m = 0, last = 0, cnt = 0; while (i <= mid && j <= r) { if (a[i] <= a[j]) { tmp[m++] = a[i]; if (a[i++] != last) ans += cnt; } else { tmp[m++] = a[j]; last = a[j++]; cnt++; } } while (i <= mid) tmp[m++] = a[i], ans += (a[i++] != last) * cnt; while (j <= r) tmp[m++] = a[j++]; FOR(i, 0, m) a[l + i] = tmp[i]; return ans; } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n; FOR(i, 0, n) cin >> a[i]; cout << cal(0, n - 1) << endl; return 0; }
Code mẫu của RR
#include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <iomanip> #include <bitset> #include <complex> #define FOR(i,a,b) for(int i = a; i <= b; ++i) #define FORD(i,a,b) for(int i = a; i >= b; --i) #define REP(i,a) for(int i = 0; i < a; ++i) #define MP make_pair #define PB push_back using namespace std; int n, a[60111], bit[60111]; #define _(x) ((x) & (-(x))) inline void update(int k) { while (k <= 60000) { bit[k]++; k += _(k); } } inline int get(int x) { int res = 0; while (x > 0) { res += bit[x]; x -= _(x); } return res; } int main() { scanf("%d", &n); FOR(i,1,n) scanf("%d", &a[i]); int res = 0; FORD(i,n,1) { res += get(a[i]-1); update(a[i]); } cout << res; return 0; }
Code mẫu của hieult
#include <cstdio> #include <cstring> //#include <conio.h> #define Max 111111 #define du 66666 using namespace std; long long dem[du+10],a[Max],kq=0; void update(int u){ while(u<=60000){ dem[u]++; u+=u&-u; } } long long tinh(int u){ long long r = 0; while(u>0){ //printf("%d\n",u); r+=dem[u]; u-=u&-u; } return r; } int main(){ // freopen("NKINV.in","r",stdin); int n,L,R; memset(dem,0,sizeof(dem)); scanf("%d",&n); a[0] = 0; for(int i = 1;i<=n;i++){ scanf("%lld",&a[i]); } for(int i = n;i>=1;i--){ kq+=tinh(a[i]-1); update(a[i]); } printf("%lld",kq); // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program NKINV; Const input = ''; output = ''; maxn = 60000; Var a: array[1..maxn] of integer; n: integer; res: integer; Procedure update(v: integer); Begin While v >= 1 do Begin inc(a[v]); v:= v - (v and (-v)); End; End; Function calc(v: integer): integer; Var t: integer; Begin t:= 0; While v <= maxn do Begin t:= t + a[v]; v:= v + (v and (-v)); End; calc:= t; End; Procedure solve; Var f: text; i,x: integer; Begin Assign(f, input); Reset(f); res:= 0; Read(f, n); Fillchar(a, sizeof(a), 0); For i:= 1 to n do Begin Read(f, x); res:= res + calc(x); update(x - 1); End; Close(f); Assign(f, output); Rewrite(f); Writeln(f, res); Close(f); End; Begin solve; End.
Code mẫu của skyvn97
#include<bits/stdc++.h> #define MAX 60060 #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1) using namespace std; int a[MAX],b[MAX],cnt[MAX],n; void init(void) { scanf("%d",&n); FOR(i,1,n) scanf("%d",&a[i]); } void process(void) { while (true) { bool allZero=true; FOR(i,1,n) if (a[i]>0) allZero=false; if (allZero) break; memset(cnt,0,sizeof cnt); FOR(i,1,n) { if (a[i]&1) cnt[a[i]]++; else b[i]+=cnt[a[i]+1]; a[i]>>=1; } } long long res=0; FOR(i,1,n) res+=b[i]; cout<<res<<endl; } int main(void) { init(); process(); return 0; }
Code mẫu của khuc_tuan
import java.io.*; import java.util.*; public class Main { static int n, result; static int[] a, b; static void tim(int l,int r) { if(l==r) return; int m = (l+r) / 2; tim( l, m); tim( m+1, r); int st = m; for(int i=l;i<=m;++i) { while(st<r && a[st+1]<a[i]) ++st; result += st - m; } int st2 = l; st = m+1; for(int i=l;i<=r;++i) { if(st2>m) b[i] = a[st++]; else if(st>r) b[i] = a[st2++]; else if(a[st]<a[st2]) b[i] = a[st++]; else b[i] = a[st2++]; } for(int i=l;i<=r;++i) a[i] = b[i]; } public static void main(String[] args) throws Exception { BufferedReader kb = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(kb.readLine()); a = new int[n]; b = new int[n]; for(int i=0;i<n;++i) a[i] = Integer.parseInt(kb.readLine()); result = 0; tim( 0, n-1); System.out.println(result); } }
Bình luận