P2346 四子连棋 - 洛谷
依旧暴力地广搜，只不过这里的状态比较复杂，需要有耐心。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define samplepassediscorrect for(;;)
#define lowbit(x) (x&(-x))
using namespace std;
struct point{
char a[6][6],flag;
int step;
};
bool check(point s){
char a[5][5];
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
a[i][j]=s.a[i][j];
for(int i=1;i<=4;i++){
if(a[i][1]==a[i][2]&&a[i][2]==a[i][3]&&a[i][3]==a[i][4]) return true;
if(a[1][i]==a[2][i]&&a[2][i]==a[3][i]&&a[3][i]==a[4][i]) return true;
}
if(a[1][1]==a[2][2]&&a[2][2]==a[3][3]&&a[3][3]==a[4][4]) return true;
if(a[4][1]==a[3][2]&&a[3][2]==a[2][3]&&a[2][3]==a[1][4]) return true;
return false;
}
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
set<string>vis;
string get(point x){
string k="";
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
k=k+x.a[i][j];
}
}
return k+x.flag;
}
int main(){
point s1,s2;
memset(s1.a,' ',sizeof(s1.a));
memset(s2.a,' ',sizeof(s2.a));
string k;
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
cin>>s1.a[i][j];
s2.a[i][j]=s1.a[i][j];
k=k+s1.a[i][j];
}
}
s1.flag='B',s2.flag='W';
vis.insert(get(s1)),vis.insert(get(s2));
s1.step=0,s2.step=0;
queue<point>r;
r.push(s1),r.push(s2);
while(!r.empty()){
point temp=r.front();
if(check(temp)){
cout<<temp.step;
return 0;
}
int x1=0,x2=0,y1=0,y2=0,cnt=0;
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
if(temp.a[i][j]=='O'){
if(!cnt) x1=i,y1=j,cnt++;
else x2=i,y2=j,cnt++;;
}
if(cnt==2) break;
}
if(cnt==2) break;
}
for(int i=0;i<4;i++){
temp=r.front();
if(temp.a[x1+dx[i]][y1+dy[i]]==temp.flag){
swap(temp.a[x1][y1],temp.a[x1+dx[i]][y1+dy[i]]);
temp.flag=(temp.flag=='B')?'W':'B';
temp.step++;
if(vis.find(get(temp))==vis.end()){
vis.insert(get(temp));
r.push(temp);
}
}
temp=r.front();
if(temp.a[x2+dx[i]][y2+dy[i]]==temp.flag){
swap(temp.a[x2][y2],temp.a[x2+dx[i]][y2+dy[i]]);
temp.flag=(temp.flag=='B')?'W':'B';
temp.step++;
if(vis.find(get(temp))==vis.end()){
vis.insert(get(temp));
r.push(temp);
}
}
}
r.pop();
}
return 0;
}P1637 三元上升子序列 - 洛谷
很明显，我们枚举中间值，在它前面找小于它的个数，在它后面找大于它的个数，相乘后累加就是答案。这里是不是很像逆序数，不过这里应该是顺序数。因为是严格的大于，所以相同的数要离散化为同一值。用两个树状数组就能轻松搞定。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define samplepassediscorrect for(;;)
#define lowbit(x) (x&(-x))
#define MAXN 50005
using namespace std;
ll n,a[MAXN],b[MAXN],ans1[MAXN],ans2[MAXN];
struct Fenwick_Tree{
ll tree[MAXN];
void add(int x,int num){
while(x<=n){
tree[x]+=num;
x+=lowbit(x);
}
}
ll search(int x){
ll re=0;
while(x){
re+=tree[x];
x-=lowbit(x);
}
return re;
}
}r1,r2;
struct point{
ll x,num;
}temp[MAXN];
bool cmp(point &s1,point &s2){return s1.x<s2.x;};
int main(){
jiasu;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
temp[i].x=a[i];
temp[i].num=i;
}
sort(temp+1,temp+1+n,cmp);
ll now=0,cnt=0;
for(int i=1;i<=n;i++){
if(now!=temp[i].x){
b[temp[i].num]=++cnt;
now=temp[i].x;
}
else b[temp[i].num]=cnt;
}
for(int i=1;i<=n;i++){
ans1[i]=r1.search(b[i]-1);
r1.add(b[i],1);
}
for(int i=n;i>=1;i--){
ans2[i]=r2.search(n)-r2.search(b[i]);
r2.add(b[i],1);
}
ll sum=0;
for(int i=1;i<=n;i++) sum+=ans1[i]*ans2[i];
cout<<sum;
return 0;
}P4868 Preprefix sum - 洛谷
依旧是线段树模板题，不需要任何改造。把a[i]改为k，就是将sum[i]——sum[n]都加上k-a[i] 前前缀和就是查询前缀和的1——x的区间和，我们用线段树来维护一次前缀和，这就用到了线段树的区间修改，区间查询的功能。 注意，修改之后a[i]要改为k
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define samplepassediscorrect for(;;)
#define lowbit(x) (x&(-x))
#define N 500005
using namespace std;
ll n,a[N],m,input[N];
struct node{
long long r,l,sum,lz;
};
struct Segment_Tree{
node tree[N];
void push_down(int i){//下传函数
if(tree[i].lz!=0){
tree[i*2].lz+=tree[i].lz;
tree[i*2+1].lz+=tree[i].lz;
tree[i*2].sum+=tree[i].lz*(tree[i*2].r-tree[i*2].l+1);
tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-tree[i*2+1].l+1);
tree[i].lz=0;
}
return;
}
void build(int i,int l,int r){//建树
tree[i].l=l,tree[i].r=r;
tree[i].lz=0;
if(l==r){
tree[i].sum=input[l];
return;
}
int mid=(l+r)/2;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
}
void add(int i,int l,int r,int k){//区间加减
if(tree[i].l>=l&&tree[i].r<=r){
tree[i].sum+=k*(tree[i].r-tree[i].l+1);
tree[i].lz+=k;
return;
}
push_down(i);
if(tree[i*2].r>=l) add(i*2,l,r,k);
if(tree[i*2+1].l<=r) add(i*2+1,l,r,k);
tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
return;
}
ll search(int i,int l,int r){//查询
if(tree[i].l>=l&&tree[i].r<=r) return tree[i].sum;
if(tree[i].r<l||tree[i].l>r) return 0;
push_down(i);
long long ans=0;
if(tree[i*2].r>=l) ans+=search(i*2,l,r);
if(tree[i*2+1].l<=r) ans+=search(i*2+1,l,r);
return ans;
}
}r;
int main(){
jiasu;
cin>>n>>m;
ll sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
input[i]=input[i-1]+a[i];
}
r.build(1,1,n);
string s;
ll x,y;
while(m--){
cin>>s;
if(s=="Query"){
cin>>x;
cout<<r.search(1,1,x)<<endl;
}
else{
cin>>x>>y;
r.add(1,x,n,y-a[x]);
a[x]=y;
}
}
return 0;
}P5057 [CQOI2006] 简单题 - 洛谷
题如其名，真的是简单题。我们只需维护每个点的操作次数，如果是奇数就是1，如果是偶数就是0。这用到线段树的区间修改，单点查询。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define samplepassediscorrect for(;;)
#define lowbit(x) (x&(-x))
#define N 500005
using namespace std;
ll n,a[N],m,input[N];
struct node{
long long r,l,sum,lz;
};
struct Segment_Tree{
node tree[N];
void push_down(int i){//下传函数
if(tree[i].lz!=0){
tree[i*2].lz+=tree[i].lz;
tree[i*2+1].lz+=tree[i].lz;
tree[i*2].sum+=tree[i].lz*(tree[i*2].r-tree[i*2].l+1);
tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-tree[i*2+1].l+1);
tree[i].lz=0;
}
return;
}
void build(int i,int l,int r){//建树
tree[i].l=l,tree[i].r=r;
tree[i].lz=0;
if(l==r){
// tree[i].sum=input[l];
return;
}
int mid=(l+r)/2;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
}
void add(int i,int l,int r,int k){//区间加减
if(tree[i].l>=l&&tree[i].r<=r){
tree[i].sum+=k*(tree[i].r-tree[i].l+1);
tree[i].lz+=k;
return;
}
push_down(i);
if(tree[i*2].r>=l) add(i*2,l,r,k);
if(tree[i*2+1].l<=r) add(i*2+1,l,r,k);
tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
return;
}
ll search(int i,int l,int r){//查询
if(tree[i].l>=l&&tree[i].r<=r) return tree[i].sum;
if(tree[i].r<l||tree[i].l>r) return 0;
push_down(i);
long long ans=0;
if(tree[i*2].r>=l) ans+=search(i*2,l,r);
if(tree[i*2+1].l<=r) ans+=search(i*2+1,l,r);
return ans;
}
}r;
int main(){
jiasu;
cin>>n>>m;
r.build(1,1,n);
ll flag,x,y;
while(m--){
cin>>flag;
if(flag==1){
cin>>x>>y;
r.add(1,x,y,1);
}
else{
cin>>x;
ll ans=r.search(1,x,x);
cout<<ans%2<<endl;
}
}
return 0;
}P9588 「MXOI Round 2」队列 - 洛谷
单调队列模拟题，我们会发现插入的数的个数就是1操作的x，那么我们累加x得到前缀和就是目前序列的长度，删去y个就是查找前缀和>=y+z的点，如果前缀和<y+z，那么肯定已经被删完了。我们得到的刚好大于等于y+z的那个点的下标，看sum[i]大于y多少，再用a[i]减去多余的数就是第z个数。 对应操作4也是现将小于等于y的点出优先队列，再查询最大值。
#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define N 200005
using namespace std;
ll t,c,a[N],n,f,x,sum[N],y;
deque<ll>q;
void put(ll x){
while(!q.empty()&&a[q.back()]<=a[x]){
q.pop_back();
}
q.push_back(x);
}
void out(ll x){
while(!q.empty()&&q.front()<x){
q.pop_front();
}
}
int main()
{
jiasu;
cin>>c>>t;
while(t--){
cin>>f;
if(f==1){
cin>>x;
a[++n]=x;
sum[n]=sum[n-1]+x;
put(n);
}
else if(f==2){
cin>>x;
y+=x;
}
else if(f==3){
cin>>x;
ll i=lower_bound(sum+1,sum+1+n,y+x)-sum;
cout<<a[i]-sum[i]+y+x<<endl;
}
else{
ll k=upper_bound(sum+1,sum+1+n,y)-sum;
out(k);
cout<<a[q.front()]<<endl;
}
}
return 0;
}