C++(g++ 7.5.0) 解法, 执行用时: 1342ms, 内存消耗: 196508K, 提交时间: 2022-11-17 21:02:11

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
const int MAXSIZE=1e6+10;
int tr[N][N];
int col[N][N];
int n,m;
inline int lowbit(int x){
	return x&(-x);
}
void add(int x,int y,int k){
	for(int i=x;i<=n;i+=lowbit(i)){
		for(int j=y;j<=m;j+=lowbit(j)) tr[i][j]+=k;
	}
}
int ask(int x,int y){
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i)){
		for(int j=y;j>0;j-=lowbit(j)) ans+=tr[i][j];
	}
	return ans;
}
void update(int x1,int y1,int x2,int y2,int k){
	add(x1,y1,k);
	add(x1,y2+1,-k);
	add(x2+1,y1,-k);
	add(x2+1,y2+1,k);
}
multiset<int> xx[MAXSIZE],yy[MAXSIZE];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>col[i][j];
			xx[col[i][j]].insert(i);yy[col[i][j]].insert(j);
		}
	}
	for(int i=1;i<=1000000;i++){
		if(xx[i].size()>=2){
			int L=*xx[i].begin(),R=*xx[i].rbegin();
            int U=*yy[i].begin(),D=*yy[i].rbegin();
            update(L,U,R,D,1);
		}
	}
	int q;cin>>q;
	while(q--){
		int op,x,y,c;
		cin>>op>>x>>y;
		if(op==1){
			if(ask(x,y)>0) cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
		}else{
			cin>>c;
			if(c==col[x][y]) continue;
			int p=col[x][y];
			col[x][y]=c;
			if(xx[p].size()>=2){
			int L=*xx[p].begin(),R=*xx[p].rbegin();
            int U=*yy[p].begin(),D=*yy[p].rbegin();
            update(L,U,R,D,-1);
		    }
		    auto it1=xx[p].lower_bound(x),it2=yy[p].lower_bound(y);
		    xx[p].erase(it1);yy[p].erase(it2);
		    if(xx[p].size()>=2){
			int L=*xx[p].begin(),R=*xx[p].rbegin();
            int U=*yy[p].begin(),D=*yy[p].rbegin();
            update(L,U,R,D,1);
		    }
		    if(xx[c].size()>=2){
			int L=*xx[c].begin(),R=*xx[c].rbegin();
            int U=*yy[c].begin(),D=*yy[c].rbegin();
            update(L,U,R,D,-1);
		    }
		    xx[c].insert(x);yy[c].insert(y);
		    if(xx[c].size()>=2){
			int L=*xx[c].begin(),R=*xx[c].rbegin();
            int U=*yy[c].begin(),D=*yy[c].rbegin();
            update(L,U,R,D,1);
		    }
		}
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1609ms, 内存消耗: 197496K, 提交时间: 2022-09-27 12:35:55

#include<iostream>
#include<vector>
#include<set>
using namespace std;

const int N=1e3+5;

int n,m,q;
int a[N][N];
int f[N][N];
vector<multiset<int>>x(N*N),y(N*N);

void add(int x,int y,int v)
{
    for(int i=x;i<=n;i+=i&-i)
     for(int j=y;j<=m;j+=j&-j)
      f[i][j]+=v;
}

int query(int x,int y)
{
    int ans=0;
    for(int i=x;i;i-=i&-i)
     for(int j=y;j;j-=j&-j)
      ans+=f[i][j];
    return ans;
}

void work(int u,int k)
{
    if(x[u].size()<2) return;
    int l1=*x[u].begin(),l2=*x[u].rbegin();
    int r1=*y[u].begin(),r2=*y[u].rbegin();
    add(l1,r1,k);
    add(l1,r2+1,-k);
    add(l2+1,r1,-k);
    add(l2+1,r2+1,k);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++) 
      {
          cin>>a[i][j];
          x[a[i][j]].insert(i);
          y[a[i][j]].insert(j);
      }
      
    for(int i=1;i<=1e6;i++) work(i,1);
    
    cin>>q;
    while(q--)
    {
        int op,i,j;
        cin>>op>>i>>j;
        if(op==1) cout<<(query(i,j)?"YES":"NO")<<'\n';
        else
        {
            int d;
            cin>>d;
            int p=a[i][j];
            if(p==d) continue;
            work(p,-1);
            x[p].erase(x[p].find(i));
            y[p].erase(y[p].find(j));
            work(p,1);
            
            work(d,-1);
            x[d].insert(i);
            y[d].insert(j);
            work(d,1);
            a[i][j]=d;
        }
    }
    return 0;
}