关键词：
分块，注意重复的值之间的处理。跟普通分块的操作一样的啦，具体可以参见‘不勤劳的图书管理员’。
#include <bits/stdc++.h> using namespace std; #define maxn 500000 #define lowbit(i) i & (-i) #define int long long int n, m, cnt, ans, B, c[200][maxn]; struct node int num, id, rank; a[30000]; int read() int x = 0; char c; c = getchar(); while(c < ‘0‘ || c > ‘9‘) c = getchar(); while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = getchar(); return x; int Get_ans(int x, int y) if(a[x].rank < a[y].rank) return 1; else if(a[x].rank > a[y].rank) return -1; return 0; bool cmp1(node a, node b) if(a.num != b.num) return a.num < b.num; return a.id < b.id; bool cmp2(node a, node b) return a.id < b.id; void update(int opt, int x, int sum) if(!x) return; for(int i = x; i <= cnt; i += lowbit(i)) c[opt][i] += sum; int query(int opt, int x) if(x < 0) return 0; int ans = 0; for(int i = x; i; i -= lowbit(i)) ans += c[opt][i]; return ans; signed main() n = read(); B = sqrt(n); for(int i = 1; i <= n; i ++) a[i].num = read(), a[i].id = i; sort(a + 1, a + 1 + n, cmp1); a[0].rank = 1; for(int i = 1; i <= n; i ++) if(a[i].num == a[i - 1].num) a[i].rank = a[i - 1].rank; else a[i].rank = ++ cnt; sort(a + 1, a + 1 + n, cmp2); for(int i = 1; i <= n; i ++) update(i / B, a[i].rank, 1); for(int i = n; i >= 1; i --) ans += query(n / B + 1, a[i].rank - 1); update(n / B + 1, a[i].rank, 1); m = read(); cout << ans << endl; for(int i = 1; i <= m; i ++) int x = read(), y = read(); if(x > y) swap(y, x); int p = x / B, q = y / B; if(a[x].rank < a[y].rank) ans ++; else if(a[x].rank > a[y].rank) ans --; if(p == q) for(int i = x + 1; i < y; i ++) ans += Get_ans(x, i) + Get_ans(i, y); swap(a[x], a[y]); printf("%lld\n", ans); continue; for(int i = x + 1; i < (p + 1) * B; i ++) if(i <= n) ans += Get_ans(x, i) + Get_ans(i, y); for(int i = q * B; i < y; i ++) ans += Get_ans(i, y) + Get_ans(x, i); for(int i = p + 1; i < q; i ++) ans = (ans - query(i, a[x].rank - 1) + query(i, a[y].rank - 1)); ans = (ans - query(i, a[x].rank) + query(i, a[y].rank)); update(p, a[x].rank, -1), update(q, a[y].rank, -1); update(q, a[x].rank, 1), update(p, a[y].rank, 1); swap(a[x], a[y]); printf("%lld\n", ans); return 0;
洛谷p2369exceededwarninga题解(代码片段)
题目传送门直接用sort排序最后输出即可。但是数组要使用shortint类型。否则会超内存。#include<bits/stdc++.h>usingnamespacestd;intn,m;shortinta[1000010];intmain()scanf("%d%d",&n,&m);for(inti=1;i<=n;i++)scanf("%d",&a[i] 查看详情
洛谷p1469找筷子题解(代码片段)
题目传送门先排序一遍，再一个一个判断是否有偶数个。注意for循环要i+=2。#include<bits/stdc++.h>usingnamespacestd;intn,a[10000010];intmain()scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);for(inti 查看详情
题解洛谷p6413[coci2008-2009#3]najkraci(代码片段)
链接分析计算出最短路后，一条边是最短路的一部分，当且仅当起点的\\(f\\)值加上该边边权等于终点的\\(f\\)值，所以跑最短路后，对\\(m\\)条边进行判定，满足该条件的加入最短路图。加入后进行拓扑排序，计算以该边作为终点... 查看详情
洛谷3768：简单的数学题——题解(代码片段)
...剩余的图是我用markdown写完然后截的图。参考洛谷第一篇题解。这个式子直观感受就需要莫比乌斯反演，大致的过程参考：BZOJ2693：jzptab那么跳过暴力推式子，我们能够得到：（如果你疑问为什么是miu(k/d)而不是miu(d)，其实二者皆... 查看详情
洛谷p1568赛跑题解(代码片段)
题目传送门这道题非常的水，只要你能搞清楚题意，将SH、KC不要混起来即可（所以我使用了结构体）#include<bits/stdc++.h>usingnamespacestd;intn,m,T,ans;intnow=-1;structnodeinta[1010],b[1010];intp;intN;SH,KC;intmain()scanf("%d%d",&n,&m 查看详情
洛谷p2036perket题解(代码片段)
题目传送门这道题可以使用dfs深搜实现，在每次递归深搜时要更新ans。#include<bits/stdc++.h>usingnamespacestd;intn,ans=2147483647,s=1,b;boolflag[15];structnodeints,b;a[15];voiddfs(intk)if(k==n)ans=min(ans,abs(s-b));for(inti=1 查看详情
洛谷p2708硬币翻转题解(代码片段)
题目传送门真如题面所说，难度系数：☆☆☆☆☆（如果你看懂了）。从后往前扫一次，如果a[i]==0&&a[i-1]==1那么将ans+2。注意最后不要忘记开头if(a[0]==‘0‘)ans++;#include<bits/stdc++.h>usingnamespacestd;chara[300];intans;intmain()cin>... 查看详情
洛谷4238：模板多项式求逆——题解(代码片段)
https://www.luogu.org/problemnew/show/P4238如题所示，对998244353取模。板子没啥好说的。讲解看这位大佬：http://blog.miskcoo.com/2015/05/polynomial-inverse#include<cstdio>#include<cctype>#include<cstring>#inclu 查看详情
洛谷p1957口算练习题题解(代码片段)
题目传送门这道题是考字符串处理，另外输入要使用c++的cin的神奇功能。#include<bits/stdc++.h>usingnamespacestd;intn;charch;inta,b;chark;stringINTtoSTRING(intx)ostringstreamoss;oss<<x;returnoss.str();intmain()scanf("%d", 查看详情
洛谷p2077红绿灯题解(代码片段)
题目传送门这道题一秒一秒的扫描一定会超时，所以就用一种O(N)的算法。#include<bits/stdc++.h>usingnamespacestd;intn,m,a[100001],b[100001],c[100001],x=0,k;intmain()scanf("%d%d",&n,&m);for(inti=1;i<n;i++)scanf("%d",& 查看详情
洛谷2765：[网络流24题]魔术球问题——题解(代码片段)
...。例如，在4根柱子上最多可放11个球。参考：洛谷前两页题解。一种做法是贪心， 查看详情
洛谷p1420最长连号题解(代码片段)
题目传送门这道题我是打暴力的。。。（尴尬）所以直接是O(N2)的时间，但好像没有炸，数据很水。。。#include<bits/stdc++.h>usingnamespacestd;intn,a[10010],ans;intmain()scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d",&a[i]);for(inti=1;i 查看详情
洛谷3953：逛公园——题解(代码片段)
https://www.luogu.org/problemnew/show/P3953策策同学特别喜欢逛公园。公园可以看成一张n个点m条边构成的有向图，且没有自环和重边。其中1号点是公园的入口，n号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的... 查看详情
洛谷p1634禽兽的传染病题解(代码片段)
题目传送门最近都在刷红色的水题。。。这道题因为是不断地传染，所以直接求幂次方就好啦。。。但是一测样例WA了。。。原来x初始需要加1。。。提交评测WA了。。。原来要开longlong。。。话不多说，下附代码：（9行威武！）... 查看详情
洛谷1578：[wc2002]奶牛浴场——题解(代码片段)
https://www.luogu.org/problemnew/show/P1578#sub由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个... 查看详情
洛谷p1652圆题解(代码片段)
题目传送门这道题也就是考你对几何的了解：圆与圆没有公共点且一个圆在另一个圆外面时，叫做圆与圆相离。当圆心距大于两圆半径之和时，称为两圆外离；当圆心距小于两圆半径之差的绝对值时，称为两圆内含。知道了以后... 查看详情
洛谷p1615西游记公司题解(代码片段)
题目传送门这道题题面写得非常好。但好像并没有什么ruan用。这道题貌似就是把时间差求出来，乘上猪八戒能偷的电脑数就好了。（注意longlong）#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llx,y,z,a,b,c;intmain()scanf("%lld:%lld:%lld... 查看详情
洛谷p1789mc生存插火把题解(代码片段)
题目传送门这道题目可以纯暴力：#include<bits/stdc++.h>//Minecraft666usingnamespacestd;inta[110][110];intn,m,k,ans;intmain()scanf("%d%d%d",&n,&m,&k);for(inti=1;i<=m;i++)intx,y;scanf("%d%d",& 查看详情