@

考虑查询的单词可能只有一个字母，特判一下 $60$ 分暴力就打满了，

修改后 60pts 做法，但会 TLE，那该怎么办呢？

请看 【题解】2025年新学期测试赛 或 真的是毒瘤题吗？- 题解（四维数组做法）

有个想法，只有操作2的话可以提前处理trie树,有操作1就废了，可以看看

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

char tu[700][700];
const int dx[3] = {0,1,1};
const int dy[3] = {1,1,0};

class Trie
{
public:
	int son[5000][26];
	int cnt[5000];
	int idx = 0;
	
	void insert(string s)
	{
		int p = 0;
		int l = s.size();
		for(int i = 0; i < l; i++)
		{
			int u = s[i]-'a';
			if(!son[p][u])
			{
				son[p][u] = ++idx;
			}
			p = son[p][u];
		}
		cnt[p]++;
	}
	
	int insert(char s, int p = 0)
	{
		int u = s-'a';
		if(!son[p][u])
		{
			son[p][u] = ++idx;
		}
		p = son[p][u];
		cnt[p]++;
		return p;
	}
	
	int query(string s)
	{
		int p = 0;
		int l = s.size();
		for(int i = 0; i < l; i++)
		{
			int u = s[i]-'a';
			if(!son[p][u]) return 0;
			p = son[p][u];
		}
		return cnt[p];
	}
}trie;

int main()
{
	int n,m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			cin >> tu[i][j];
		}
	}
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{ 
			int p = trie.insert(tu[i][j]);
			for(int k = 0; k < 3; k++)
			{
				int x = i;
				int y = j;
				int t = p;
				while(true)
				{
					x += dx[k];
					y += dy[k];
					if(x > n || y > m) break;
					t = trie.insert(tu[x][y], t);
				}
			}		
		}
	}
	
	int q;
	cin >> q;
	while(q--)
	{
		int type;
		cin >> type;
		if(type == 1)
		{
			int x,y;
			char c;
			cin >> x >> y >> c;
			tu[x][y] = c;
		}
		else
		{
			string s;
			cin >> s;
			
			cout << trie.query(s) << '\n';
		}
	}
	
	
	
	return 0;
}