求逆序对的板子题
#include<cstdio> #define ll long long using namespace std; const int maxn=1e5+5; ll a[maxn],r[maxn],n; ll ans=0; void msort(ll s,ll t) { if(s==t) return; ll mid=s+t>>1; msort(s,mid),msort(mid+1,t); ll i=s,j=mid+1,k=s; while(i<=mid&&j<=t) if(a[i]<=a[j]) r[k++]=a[i++]; else r[k++]=a[j++],ans+=(ll)mid-i+1; while(i<=mid) r[k]=a[i],k++,i++; while(j<=t) r[k]=a[j],k++,j++; for(int i=s; i<=t; i++) a[i]=r[i]; } inline ll read() { char ch=getchar(); ll sum=0,k=1; while(ch<'0'||ch>'9') { if(ch=='-') k=-1; ch=getchar(); } while(ch>='0'&&ch<='9') sum=sum*10+(ch^48),ch=getchar(); return sum*k; } int main() { scanf("%lld",&n); for(int i=1; i<=n; i++) a[i]=read(); msort(1,n); printf("%lld ",ans); return 0; }
unsigned long long等数据类型的定义方法的巧用
（直接long long居然也可以水到90分.）
#include<cstdio> using namespace std; int main() { unsigned long long n; scanf("%llu",&n); printf("%llu",n*n); return 0; }
单调队列
对于每一个数记录他是第几个放入的
放入时遇到比他小的元素就弹掉
这样保证了队首就是最大值
进行弹出操作时只要关注弹的次数是否等于队首元素id就可以了
（copy大佬的题解）
#include<cstdio> #include<utility> #include<deque> #include<algorithm> using namespace std; int n,num,cnt; deque<pair<int,int> >q; void solu1(int x,int n) { while(q.size() != 0 && q.back().first< x) { q.pop_back(); } q.push_back(make_pair(x,n)); } void solu2(int x) { while(q.front().second <= x && q.size() != 0) q.pop_front(); } int main() { scanf("%d",&n); int opt; for(int i = 1; i <= n; i++) { scanf("%d",&opt); if(opt == 1) { int x; scanf("%d",&x); solu1(x,++num); } if(opt == 2) { solu2(++cnt); } if(q.size() == 0) printf("-1 "); else printf("%d ",q.front().first); } return 0; }
(大概是我写两个cmp是不对的
（一个就够了qwq）
（于是爆0.
#include<cstdio> #include<algorithm> #include<deque> using namespace std; struct shu { int x,y; }; shu c[maxn+5]; int n; bool cmp(shu a,shu b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&c[i].x,&c[i].y); } sort(c+1,c+n+1,cmp); for(int i=1;i<=n;i++) { printf("%d %d ",c[i].x,c[i].y); } return 0; }
双向队列的基本操作
#include<cstdio> #include<algorithm> #include<deque> using namespace std; int n,opt; deque<int>q; int main() { scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&opt); if(opt == 1) { int x; scanf("%d",&x); if(q.size() == 0) printf("-1 "); else printf("%d ",q.back()); q.push_back(x); } else if(opt == 2) { if(q.size() == 0) printf("-1 "); else { printf("%d ",q.back()); q.pop_back(); } } else if(opt == 3) { int x,y; scanf("%d%d",&x,&y); if(q.size()<=x) printf("-1 "); else { printf("%d ",q[x]); q[x]=y; } } else if(opt == 4) { int x; scanf("%d",&x); if(q.size() == 0) printf("-1 "); else printf("%d ",q.front()); q.push_front(x); } else if(opt == 5) { if(q.size() == 0) printf("-1 "); else { printf("%d ",q.front()); q.pop_front(); } } } return 0; }
开两个栈，一个用来模拟真实的栈，另一个求最大值。
每当加入新元素时
如果该元素大于等于栈顶元素 就压进去
弹出元素时，如果真实栈的弹出元素和最大值栈的栈顶元素相等，就弹出。
（qxt好gou啊.
//实现一个栈，支持push和pop，每次执行完毕后要输出栈内元素的最大值 #include<cstdio> #include<stack> using namespace std; stack<int> q,pq; int n; void solu1(int x) { q.push(x); if(pq.size() == 0 || pq.top() <= x) pq.push(x); } void solu2() { if(q.size()) { if(pq.size()) if(q.top() == pq.top()) { q.pop(); pq.pop(); } else q.pop(); else q.pop(); } } int main() { scanf("%d",&n); int opt; for(int i = 1; i <= n; i++) { scanf("%d",&opt); if(opt == 1) { int x; scanf("%d",&x); solu1(x); } if(opt == 2) { solu2(); } if(pq.size() == 0) printf("-1 "); else printf("%d ",pq.top()); } return 0; }